### Abstract

Original language | English |
---|---|

Pages (from-to) | 471-484 |

Journal | International Journal of Computational Geometry and Applications |

Volume | 20 |

Issue number | 4 |

DOIs | |

Publication status | Published - 2010 |

### Fingerprint

### Cite this

*International Journal of Computational Geometry and Applications*,

*20*(4), 471-484. https://doi.org/10.1142/S0218195910003396

}

*International Journal of Computational Geometry and Applications*, vol. 20, no. 4, pp. 471-484. https://doi.org/10.1142/S0218195910003396

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

Research output: Contribution to journal › Article › Academic › peer-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 -