Voronoi Diagram of Polygonal Chains Under the Discrete Frechet Distanceby S. Bereg, K. Buchin, M. Buchin, M. Gavrilova, and B. Zhu
Figure 1: The relationship between discrete (blue) and continuous (red) Frechet distances. 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 (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 are summarized as follows.
@article{bbbgz-vdpc-10 , author = {Sergey Bereg and Kevin Buchin and Maike Buchin and Marina Gavrilova and Binhai Zhu} , title = {Voronoi Diagram of Polygonal Chains under the Discrete {F}r{\'e}chet Distance} , journal = {Int. J. Comput. Geom. Appl.} , year = {2010} , volume = {20} , pages = {471--484} , url = {http://dx.doi.org/10.1142/S0218195910003396} } |