Computing The Packedness of Curves

Abstract

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

References in corpus (2)

• Point-Location in The Arrangement of Curves
• Approximating the packedness of polygonal curves