Simplifying 3D Polygonal Chains Under the Discrete Frchet Distance

详细信息    查看全文

• 作者：Sergey Bereg ; Minghui Jiang ; Wencheng Wang ; Boting Yang ; Binhai Zhu
• 刊名：Lecture Notes in Computer Science
• 出版年：2008
• 出版时间：2008
• 年：2008
• 卷：4957
• 期：1
• 页码：630-641
• 全文大小：511.0 KB

文摘

A well-known measure to characterize the similarity of two polygonal chains is the famous Fr¨¦chet distance. In this paper, for the first time, we consider the problem of simplifying 3D polygonal chains under the discrete Fr¨¦chet distance. We present efficient polynomial time algorithms for simplifying a single chain, including the first near-linear O(nlogn) 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.