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

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

    Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

    2 Citaten (Scopus)

    Samenvatting

    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 Ω(n dk ) for dimension d = 1,2; and Ω(n d(k − 1) + 2) for dimension d > 2.
    Originele taal-2Engels
    TitelComputing and Combinatorics
    Subtitel 14th Annual International Conference, COCOON 2008, Dalian, China, June 27-29, 2008 Proceedings
    RedacteurenX. Hu, J. Wang
    Plaats van productieBerlin
    UitgeverijSpringer
    Hoofdstuk35
    Pagina's352-362
    Aantal pagina's11
    ISBN van elektronische versie978-3-540-69733-6
    ISBN van geprinte versie978-3-540-69732-9
    DOI's
    StatusGepubliceerd - 2008

    Publicatie series

    NaamLecture Notes in Computer Science (LNCS)
    Volume5092
    ISSN van geprinte versie0302-9743

    Vingerafdruk Duik in de onderzoeksthema's van 'Voronoi diagram of polygonal chains under the discrete Fréchet distance'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit