Voronoi Diagram of Polygonal Chains Under the Discrete Frechet Distance

by 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.

  • The combinatorial complexity of VDF(C) is at most O(ndk+epsilon)
  • The combinatorial complexity of VDF (C) is at least Omega(ndk) for dimension d=1,2; and Omega(nd(k 1)+2) for dimension d > 2.
Keywords: Voronoi diagram, Frechet distance, discrete Frechet distance, combinatorial complexity, protein structure alignment.

pdf file

, 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}