We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
VORONOI DIAGRAM OF POLYGONAL CHAINS UNDER THE DISCRETE FRÉCHET DISTANCE.
- Authors
BEREG, SERGEY; BUCHIN, KEVIN; BUCHIN, MAIKE; GAVRILOVA, MARINA; ZHU, BINHAI
- 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 (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(ndk+∊). • The combinatorial complexity of $VD_F (\mathcal{C})$ is at least Ω(ndk) for dimension d = 1, 2; and Ω(nd(k-1)+2) for dimension d > 2.
- Subjects
VORONOI polygons; FRECHET spaces; GEOMETRY; MATHEMATICS; PROTEIN structure
- Publication
International Journal of Computational Geometry & Applications, 2010, Vol 20, Issue 4, p471
- ISSN
0218-1959
- Publication type
Article
- DOI
10.1142/S0218195910003396