TY - JOUR

T1 - Voronoi diagram of polygonal chains under the discrete Fréchet distance

AU - Bereg, S.

AU - Buchin, K.

AU - Buchin, M.

AU - Gavrilova, M.L.

AU - Zhu, B.

PY - 2010

Y1 - 2010

N2 - 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 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(C).
Our main results are summarized as follows.
* The combinatorial complexity of VD_F(C) is at most O(n^(dk+¿)).
* The combinatorial complexity of VD_F(C) is at least O(n^(dk)) for dimension d = 1, 2; and O(n^(d(k-1)+2)) for dimension d > 2.

AB - 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 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(C).
Our main results are summarized as follows.
* The combinatorial complexity of VD_F(C) is at most O(n^(dk+¿)).
* The combinatorial complexity of VD_F(C) is at least O(n^(dk)) for dimension d = 1, 2; and O(n^(d(k-1)+2)) for dimension d > 2.

U2 - 10.1142/S0218195910003396

DO - 10.1142/S0218195910003396

M3 - Article

VL - 20

SP - 471

EP - 484

JO - International Journal of Computational Geometry and Applications

JF - International Journal of Computational Geometry and Applications

SN - 0218-1959

IS - 4

ER -