Computing the Exact Packedness of a Curve

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(\frac{\log (L/\delta)}{\epsilon}n^3)$ and $O(\frac{\log (L/\delta)}{\epsilon}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 time in the worst-case and only uses intersection information to solve the problem.