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


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
Number of pages12
ISBN (Print)3540388753, 9783540388753
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


Other14th Annual European Symposium on Algorithms, ESA 2006

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


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

Cite this