Computing the Exact Packedness of a Curve

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(\frac{\log (L/\delta)}{\epsilon}n^3)$ and $O(\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.