A polygonal curve P with n vertices is c-packed, if the sum of the lengths of the parts of the edges of the curve that are inside any disk of radius r is at most cr, for any r>0. Similarly, the concept of c-packedness can be defined for any scaling of a given shape. Assuming L is the total length of P and \delta is the minimum distance between any pair of points on two non-intersecting edges of P, ({\epsilon}n^3) time algorithm is } 1+\epsilon ) -approximation algorithms exist for disks, and for convex polygons of constant size, with time complexities O(\frac{\log (L/\delta){\epsilon}n ^3) and O(\log (L/\delta){\epsilon^{5/2}}n^3\log} {\epsilon^3})^{\frac 4 3}}\polylog  n ), respectively. There also exist two algorithms with approximation factor more than 2, for the c-packedness using axis-aligned hypercubes instead of disks, where they consider the shapes centered at the vertices of the curve when determining the c-packedness. We call this measure the vertex-relative c-packedness. For axis-aligned squares instead of disks, a related concept called relative-length was already discussed and it has an exact{\epsilon})+n{\epsilon}) time algorithm, and the existing } O(n ^3) algorithm. We show that vertex-relative c-packedness has approximation factor at least 2 for c-packedness. We design the first exact algorithmfor computing the minimum c for which a given curve P is c-packed. Our algorithm runs in O(n^5) time . We also give a data-structure for computing the length of the curve inside arbitrary query disk, known as the length-query problem . It has O(n^6\log n) construction time, uses O(n^6) space, and has query time O(\log n+k), where k is the number of intersected segments with the query shape  .
A polygonal curve P with n vertices is c-packed, if the sum of the lengths of the parts of the edges of the curve that are inside any disk of radius r is at most cr, for any r>0. Similarly, the concept of c-packedness can be defined for any scaling of a given shape. Assuming L is the diameter of P and \delta is the minimum distance between points on disjoint edges of P, we show the approximation factor of the existing O(\frac{\log (L/\delta){\epsilon}n^3) time algorithm is } 1+\epsilon -approximation {\epsilon}n ^3) and O(\log (L/\delta){\epsilon^{5/2}}n^3\log} algorithm. The massively parallel versions of these algorithms run in O(\log (L/\delta)) rounds. We improve the existing O((\frac{n{\epsilon^3})^{\frac 4 3}}\polylog \frac n \epsilon) time (6+\epsilon)-approximation algorithm by providing a (4+\epsilon)-approximation O( n (\log^2 n)(\log^2 \frac{1{\epsilon})+n{\epsilon}) time algorithm, and the existing } O(n ^2) time 2-approximation algorithm improving the existing O(n^2\log n) time 2-approximation algorithm. Our exact c-packedness algorithm takes O(n^5) time , which is the first exact algorithm for disks. We show using \alpha-fat shapes instead of disks adds a factor \alpha^2 to the approximation. We also give a data-structure for computing the curve-length inside query disks . It has O(n^6\log n) construction time, uses O(n^6) space, and has query time O(\log n+k), where k is the number of intersected segments with the query shape . We also give a massively parallel algorithm for relative c-packedness with O(1) rounds .
R
total length
diameter
R
any pair of points on two non-intersecting
points on disjoint
R
(
we show the approximation factor of the existing O(\frac{\log (L/\delta)
D
)
D
algorithms exist for disks, and for convex polygons of constant size, with time complexities O(\frac{\log (L/\delta)
A
algorithm. The massively parallel versions of these algorithms run in O(\log (L/\delta)) rounds. We improve the existing O((\frac{n
A
\frac n \epsilon) time (6+\epsilon)-approximation algorithm by providing a (4+\epsilon)-approximation O(
R
), respectively. There also exist two algorithms with approximation factor more than 2, for the c-packedness using axis-aligned hypercubes instead of disks, where they consider the shapes centered at the vertices of the curve when determining the c-packedness. We call this measure the vertex-relative c-packedness. For axis-aligned squares instead of disks, a related concept called relative-length was already discussed and it has an exact
(\log^2 n)(\log^2 \frac{1
R
^3) algorithm. We show that vertex-relative c-packedness has approximation factor at least 2 for c-packedness. We design the first exact algorithmfor computing the minimum c for which a given curve P is c-packed. Our algorithm runs in
^2) time 2-approximation algorithm improving the existing O(n^2\log n) time 2-approximation algorithm. Our exact c-packedness algorithm takes
R
. We
, which is the first exact algorithm for disks. We show using \alpha-fat shapes instead of disks adds a factor \alpha^2 to the approximation. We
R
length of the curve inside arbitrary query disk, known as the length-query problem
curve-length inside query disks
A
. We also give a massively parallel algorithm for relative c-packedness with O(1) rounds