Voronoi Diagram of Polygonal Chains under the Discrete Frechet Distance

摘要：

Polygonal chains are fundamental objects in many applications like pattern recognition and protein structure alignment. A well-known measure to characterize the similarity of two polygonal chains is the (continuous/discrete) Frechet distance. In this paper, for the first time, we consider the Voronoi diagram of polygonal chains in d-dimension under the discrete Frechet distance. Given a set C of n polygonal chains in d-dimension, each with at most k vertices, we prove fundamental properties of such a Voronoi diagram VDf(C). Our main results axe summarized as follows. — The combinatorial complexity of VDf(C) is at most O(ndk+C). — The combinatorial complexity of VDf(C) is at least Ω(ndk) for dimension d=1,2; and Ω(nd(k-1)+2) for dimension d > 2.

作者: Sergey Bereg Kevin Buchin Maike Buchin Marina Gavrilova Binhai Zhu

作者单位: Department of Computer Science, University of Texas at Dallas,Richardson, TX 75083, USA Department of Information and Computing Sciences,Universiteit Utrecht, The Netherlands Department of Information and Computing Sciences,Universiteit Utrecht,The Netherlands Department of Computer Science,University of Calgary, Calgary,Alberta T2N 1N4, Canada Department of Computer Science, Montana State University,Bozeman, MT 59717-3880, USA

会议类型: 国际会议

会议名称: The 4th Annual International Computing and Combinatorics Conference,COCOON 2008(第14届国际计算和组合会议)

会议地点: 大连

会议语种:英文

页码: 352-362

在线出版日期: 2008-06-01（万方平台首次上网日期，不代表论文的发表时间）