论文标题
近似多边形曲线的填料
Approximating the packedness of polygonal curves
论文作者
论文摘要
2012年，Driemel等人。 \ cite {dblp：journals/dcg/driemelhw12}引入了$ c $包装曲线的概念，作为现实的输入模型。在$ c $是常数的情况下，他们给出了接近线性的时间$（1+ \ varepsilon）$ - 用于计算两个$ c $ c $包装的多边形曲线之间的fréchet距离的近似算法。从那时起，许多论文都使用了模型。 在本文中，我们考虑了计算最小的$ c $的问题，在$ \ mathbb {r}^d $中，给定的多边形曲线是$ c $ - 包装。我们提出两种近似算法。第一种算法是$ 2 $ - APPROXIMATION算法，以$ O（Dn^2 \ log N）$时间运行。在情况下，$ d = 2 $，我们开发了更快的算法，该算法返回$（6+ \ varepsilon）$ - 近似值，并以$ o（（（n/\ varepsilon^3）^{4/3} {4/3} polylog（n/\ varepsilon））运行。 我们还实施了第一个算法，并计算了16组实际轨迹的近似包装值。实验表明，$ c $包装的概念是许多曲线和轨迹的有用的现实输入模型。
In 2012 Driemel et al. \cite{DBLP:journals/dcg/DriemelHW12} introduced the concept of $c$-packed curves as a realistic input model. In the case when $c$ is a constant they gave a near linear time $(1+\varepsilon)$-approximation algorithm for computing the Fréchet distance between two $c$-packed polygonal curves. Since then a number of papers have used the model. In this paper we consider the problem of computing the smallest $c$ for which a given polygonal curve in $\mathbb{R}^d$ is $c$-packed. We present two approximation algorithms. The first algorithm is a $2$-approximation algorithm and runs in $O(dn^2 \log n)$ time. In the case $d=2$ we develop a faster algorithm that returns a $(6+\varepsilon)$-approximation and runs in $O((n/\varepsilon^3)^{4/3} polylog (n/\varepsilon)))$ time. We also implemented the first algorithm and computed the approximate packedness-value for 16 sets of real-world trajectories. The experiments indicate that the notion of $c$-packedness is a useful realistic input model for many curves and trajectories.
