This is the authors' abstract. We don't add key points for this paper.
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 $δ$ is the minimum distance between points on disjoint edges of P, we show the approximation factor of the existing O(log (L/δ)εn³) time algorithm is $1+ε$-approximation algorithm. The massively parallel versions of these algorithms run in O(log (L/δ)) rounds. We improve the existing O((n/ε³)4 3 n ε) time $(6+ε)$-approximation algorithm by providing a $(4+ε)$-approximation O(n(log² n)(log² 1ε)+nε) time algorithm, and the existing O(n²) time $2$-approximation algorithm improving the existing O(n²log n) time $2$-approximation algorithm. Our exact c-packedness algorithm takes O(n⁵) time, which is the first exact algorithm for disks. We show using $α$-fat shapes instead of disks adds a factor α² to the approximation. We also give a data-structure for computing the curve-length inside query disks. It has O(n⁶log n) construction time, uses O(n⁶) 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.
Answers are grounded in this paper and cite their sources.
No takes yet. Share an insight, caveat, or question.
Aghamolaei et al. (2020) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: