Simplifying 3D Polygonal Chains Under the Discrete Fréchet Distance
Simplifying 3D Polygonal Chains Under the Discrete Fréchet Distance
复制标题
简化离散 Fréchet 距离下的 3D 多边形链
DOI：
10.1007/978-3-540-78773-0_54
复制
发表时间：
2008
影响因子：
3.2
通讯作者：
B. Zhu
中科院分区：
文献类型：
--
作者：
S. Bereg;Minghui Jiang;Wencheng Wang;Boting Yang;B. Zhu
描述两个多边形链相似性的一个众所周知的度量是著名的弗雷切特距离。在本文中，我们首次考虑离散Frechet距离下简化3D多边形链的问题。我们提出了用于简化单链的高效多项式时间算法，包括用于连续 min-# 拟合问题的第一个近线性 O(n log n) 时间精确算法。我们的算法推广到任何固定维度 d > 3。在基于岭的模型简化的推动下，我们还考虑同时简化一对链，并且我们表明一般问题的一个版本是 NP 完全的。
A well-known measure to characterize the similarity of two polygonal chains is the famous Frechet distance. In this paper, for the first time, we consider the problem of simplifying 3D polygonal chains under the discrete Frechet distance. We present efficient polynomial time algorithms for simplifying a single chain, including the first near-linear O(n log n) time exact algorithm for the continuous min-# fitting problem. Our algorithms generalize to any fixed dimension d > 3. Motivated by the ridge-based model simplification we also consider simplifying a pair of chains simultaneously and we show that one version of the general problem is NP-complete.