Approximating the Fréchet Distance for Realistic Curves in Near Linear Time
Approximating the Fréchet Distance for Realistic Curves in Near Linear Time
复制标题
近似线性时间内真实曲线的 Fréchet 距离
DOI：
10.1145/1810959.1811019
复制
发表时间：
2010
影响因子：
0.8
通讯作者：
C. Wenk
中科院分区：
文献类型：
--
作者：
Anne Driemel;Sariel Har;C. Wenk
本文给出了一个简单实用的计算两条多边形曲线间Fréchet距离的（1+ε）-近似算法。为了分析这个算法，我们引入了一个新的现实家庭的曲线，c-填充曲线，这是封闭的简化。我们相信c-填充曲线的概念是独立的兴趣。我们表明，我们的算法具有接近线性的运行时间的c-包装多边形曲线，和其他输入模型，如低密度多边形曲线类似的结果。
We present a simple and practical (1+ε)-approximation algorithm for the Fréchet distance between two polygonal curves in ℝd. To analyze this algorithm we introduce a new realistic family of curves, c-packed curves, that is closed under simplification. We believe the notion of c-packed curves to be of independent interest. We show that our algorithm has near linear running time for c-packed polygonal curves, and similar results for other input models, such as low-density polygonal curves.