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

S. Bereg, K. Buchin, M. Buchin, M.L. Gavrilova, B. Zhu

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)
3 Downloads (Pure)

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 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.
Original languageEnglish
Pages (from-to)471-484
JournalInternational Journal of Computational Geometry and Applications
Volume20
Issue number4
DOIs
Publication statusPublished - 2010

Fingerprint

Voronoi Diagram
Pattern recognition
Proteins
Combinatorial Complexity
Protein Structure
Pattern Recognition
Alignment

Cite this

@article{3e26a4c1bdc445c3b39ae084a83cbd8c,
title = "Voronoi diagram of polygonal chains under the discrete Fr{\'e}chet distance",
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{\'e}chet distance. In this paper, for the first time, we consider the Voronoi diagram of polygonal chains in d-dimension under the discrete Fr{\'e}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.",
author = "S. Bereg and K. Buchin and M. Buchin and M.L. Gavrilova and B. Zhu",
year = "2010",
doi = "10.1142/S0218195910003396",
language = "English",
volume = "20",
pages = "471--484",
journal = "International Journal of Computational Geometry and Applications",
issn = "0218-1959",
publisher = "World Scientific",
number = "4",

}

Voronoi diagram of polygonal chains under the discrete Fréchet distance. / Bereg, S.; Buchin, K.; Buchin, M.; Gavrilova, M.L.; Zhu, B.

In: International Journal of Computational Geometry and Applications, Vol. 20, No. 4, 2010, p. 471-484.

Research output: Contribution to journalArticleAcademicpeer-review

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 -