@inproceedings{0ff77b4618054e94be4d8f48b7ed97a6,
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 Ω(n dk ) for dimension d = 1,2; and Ω(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 = "2008",
doi = "10.1007/978-3-540-69733-6\_35",
language = "English",
isbn = "978-3-540-69732-9",
series = "Lecture Notes in Computer Science (LNCS)",
publisher = "Springer",
pages = "352--362",
editor = "X. Hu and J. Wang",
booktitle = "Computing and Combinatorics",
address = "Germany",
}