Computing the Fréchet distance between simple polygons

K. Buchin, M. Buchin, C. Wenk

    Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

    33 Citaten (Scopus)

    Samenvatting

    We present the first polynomial-time algorithm for computing the Fréchet distance for a non-trivial class of surfaces: simple polygons, i.e., the area enclosed by closed simple polygonal curves, which may lie in different planes. For this, we show that we can restrict the set of maps realizing the Fréchet distance, and develop an algorithm for computing the Fréchet distance using the algorithm for curves, techniques for computing shortest paths in a simple polygon, and dynamic programming.
    Originele taal-2Engels
    Pagina's (van-tot)2-20
    TijdschriftComputational Geometry
    Volume41
    Nummer van het tijdschrift1-2
    DOI's
    StatusGepubliceerd - 2008

    Vingerafdruk Duik in de onderzoeksthema's van 'Computing the Fréchet distance between simple polygons'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit