论文标题
计算曲线的包装
Computing The Packedness of Curves
论文作者
论文摘要
$ n $顶点的多边形曲线$ p $是$ c $包装的，如果曲线边缘的零件的长度总和在半径$ r $的任何磁盘中最多都是$ cr $，则对于任何$ r> 0 $。同样，可以为给定形状的任何缩放定义$ c $包装的概念。 假设$ l $是$ p $的直径，$δ$是$ p $的分离边缘上点之间的最小距离，我们显示现有$ o（\ frac {\ frac {\ log log（l/δ）}εn^3）$ time time time Algorithm为$ 1+ε$ -Approximation algorximation Algorithm。这些算法的大量并行版本以$ o（\ log（l/δ））$ roughs运行。我们改善现有$ o（（（\ frac {n} {ε^3}）^{\ frac 4 3} \ polylog \ fracnε）$ time $（6+ε）$ - 近似算法通过提供$（4+ε）$（4+ε）$ - 近似$ o（n（4+ε）） \ frac {1}ε）+\ frac {n}ε）$ time算法和现有的$ o（n^2）$ o（n^2）$ 2 $ 2 $ 2 $ - approximation算法改善现有$ O（n^2 \ log n）$ 2 $ 2 $ 2 $ 2 $ -2 $ -2 $ -2 $ -2 $ -2 $ -2 $ -2 $ -APPROXIMATION ALGORITHM。 我们的确切$ c $ - 包装算法需要$ o（n^5）$时间，这是磁盘的第一个精确算法。我们使用$α$ -FAT形状而不是磁盘显示为近似值增加一个因子$α^2 $。 我们还提供了用于计算查询磁盘内曲线长度的数据结构。它具有$ o（n^6 \ log n）$构造时间，使用$ o（n^6）$ space，并且具有查询时间$ o（\ log n+k）$，其中$ k $是具有查询形状的相交段的数量。我们还为相对$ c $包的相对$ o（1）$ rounds提供了一种平行的算法。
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(\frac{\log (L/δ)}εn^3)$ time algorithm is $1+ε$-approximation algorithm. The massively parallel versions of these algorithms run in $O(\log (L/δ))$ rounds. We improve the existing $O((\frac{n}{ε^3})^{\frac 4 3}\polylog \frac n ε)$ time $(6+ε)$-approximation algorithm by providing a $(4+ε)$-approximation $O(n(\log^2 n)(\log^2 \frac{1}ε)+\frac{n}ε)$ 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 $α$-fat shapes instead of disks adds a factor $α^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.
