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 Berlin Heidelberg
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

    Aronov, B., Har-Peled, S., Knauer, C., Wang, Y., & Wenk, C. (2006). Fréchet distance for curves, revisited. In Algorithms, ESA 2006 - 14th Annual European Symposium, Proceedings (pp. 52-63). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4168 LNCS). Springer-Verlag Berlin Heidelberg. https://doi.org/10.1007/11841036_8