Voronoi diagram of polygonal chains under the discrete Fréchet 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) Fréchet distance. In this paper, for the first time, we consider the Voronoi diagram of polygonal chains in d-dimension under the discrete Fréchet distance. Given a set $mathcal{C}$ of n polygonal chains in d-dimension, each with at most k vertices, we prove fundamental properties of such a Voronoi diagram $VD-F (mathcal{C})$. Our main results are summarized as follows. ? The combinatorial complexity of $VD-F (mathcal{C})$ is at most O(n~(dk+)). ? The combinatorial complexity of $VD-F (mathcal{C})$ is at least Ω(n~(dk)) for dimension d = 1, 2; and Ω(n ~(d(k-1)+2)) for dimension d > 2.