Voronoi Diagram of Polygonal Chains under the Discrete Fréchet Distance

2007/05/19 by Bereg, Sergey, Gavrilova, Marina, Zhu, Binhai
#Computational Complexity (cs.CC) #Computational Geometry (cs.CG) #F.2.2 #FOS: Computer and information sciences #G.2.1

paper · doi:10.48550/arxiv.0705.2835

Abstract

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 famous Frèchet distance. In this paper, for the first time, we consider the Voronoi diagram of polygonal chains in d-dimension (d=2,3) under the discrete Frèchet distance. Given n polygonal chains \cal C in d-dimension (d=2,3), each with at most k vertices, we prove fundamental properties of such a Voronoi diagram \em VD_F(\cal C) by presenting the first known upper and lower bounds for \em VD_F(\cal C).

Related

• Lower Bounds for the Complexity of the Voronoi Diagram of Polygonal Curves under the Discrete Frechet Distance
• The k-Fréchet distance
• Voronoi diagrams of algebraic varieties under polyhedral norms
• Fréchet Distance for Curves, Revisited
• The Discrete Fréchet Gap