Fréchet distance for curves, revisited

Boris Aronov, Sariel Har-Peled, Christian Knauer, Yusu Wang, Carola Wenk

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    We revisit the problem of computing the Fréchet distance between polygonal curves, focusing on the discrete Fréchet distance, where only distance between vertices is considered. We develop efficient approximation algorithms for two natural classes of curves: κ-bounded curves and backbone curves, the latter of which are widely used to model molecular structures. We also propose a pseudo-output-sensitive algorithm for computing the discrete Fréchet distance exactly. The complexity of the algorithm is a function of the complexity of the free-space boundary, which is quadratic in the worst case, but tends to be lower in practice.

    Original languageEnglish (US)
    Title of host publicationAlgorithms, ESA 2006 - 14th Annual European Symposium, Proceedings
    PublisherSpringer Verlag
    Pages52-63
    Number of pages12
    ISBN (Print)3540388753, 9783540388753
    DOIs
    StatePublished - 2006
    Event14th Annual European Symposium on Algorithms, ESA 2006 - Zurich, Switzerland
    Duration: Sep 11 2006Sep 13 2006

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume4168 LNCS
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Other

    Other14th Annual European Symposium on Algorithms, ESA 2006
    CountrySwitzerland
    CityZurich
    Period9/11/069/13/06

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Computer Science(all)

    Fingerprint Dive into the research topics of 'Fréchet distance for curves, revisited'. Together they form a unique fingerprint.

    Cite this