A  curve P with n vertices is said to be c-packed if the length of the curve within any disk of radius r is at most cr, for any r>0. If the ratio \frac L \delta is fixed, where L is the total length of P and \delta is the minimum distance between any two points on P, other than the intersection points, a 2 (1+\epsilon)-approximation algorithm exists for disks, and a (1+\epsilon)-approximation algorithm exists for convex polygons  , with time complexities O(\log (L/\delta){\epsilon}n^3) and O( \frac{\log (L/\delta){\epsilon}} {\epsilon^{5/2}}} n^3\log n), respectively. Recently, two other algorithms were claimed to be constant-factor approximations for the c-packedness using axis-aligned cubes instead of disks, which only consider the vertices of the curve when determining the c-packedness and therefore contradict the original definition of the c-packedness that has no assumptions on the placement of the disks. Call this measure the relative c-packedness. Using an example, we show that c-packedness and relative c-packedness are not within a constant factor of each other . We design the first exact algorithm for computing the minimum c for which a given curve P is c-packed. Our algorithm runs in O(n^5) time. Also, we show that there are no constant-factor approximation algorithms that solve the problem in sub-quadratic timein the worst-case and only uses intersection information to solve the problem .
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, (1+\epsilon)-approximation algorithms exist for disks, and for convex polygons of constant size , with time complexities O(\log (L/\delta){\epsilon}n^3) and O( {\epsilon}} \frac{\log (L/\delta){\epsilon^{5/2}}} n^3\log 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 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 algorithm for 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
D
said to be
R
if the length of the curve within
, if the sum of the lengths of the parts of the edges of the curve that are inside
R
If the ratio \frac L \delta is fixed, where L is
Similarly, the concept of c-packedness can be defined for any scaling of a given shape. Assuming L is
R
two points on P, other than the intersection points, a 2
pair of points on two non-intersecting edges of P,
R
algorithm exists
algorithms exist
D
a (1+\epsilon)-approximation algorithm exists
A
of constant size
D
\frac{\log (L/\delta)
A
\frac{\log (L/\delta)
R
Recently, two other algorithms were claimed to be constant-factor approximations
There also exist two algorithms with approximation factor more than 2,
R
cubes
hypercubes
R
which only consider the
where they consider the shapes centered at the
R
and therefore contradict the original definition of the c-packedness that has no assumptions on the placement of the disks. Call
. We call
R
relative
vertex-relative
R
Using an example, we show that
For axis-aligned squares instead of disks, a related concept called relative-length was already discussed and it has an exact O(n^3) algorithm. We show that vertex-relative
R
and relative
has approximation factor at least 2 for
D
are not within a constant factor of each other
R
Also, we show that there are no constant-factor approximation algorithms that solve the problem in sub-quadratic timein the worst-case and only uses intersection information to solve the problem
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