Computing The Packedness of Curves

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\mathrm{/}\delta )}{ϵ}{n}^3)$ time algorithm is $1+ϵ$-approximation algorithm. The massively parallel versions of these algorithms run in $O(\log (L\mathrm{/}\delta ))$ rounds. We improve the existing $O((\frac{n}{{ϵ}^3}{)}^{\frac{4}{3}}\text{polylog}\frac{n}{ϵ})$ time $(6+ϵ)$-approximation algorithm by providing a $(4+ϵ)$-approximation $O(n(\log^2 n)(\log^2 \frac{1}{\epsilon})+\frac{n}{\epsilon})$timealgorithm,andtheexisting$O(n^2)$time$2$-approximationalgorithmimprovingtheexisting$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.