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 Dive into the research topics of 'Voronoi diagram of polygonal chains under the discrete Fréchet distance'. Together they form a unique fingerprint.

Cite this