Approximating the Fréchet distance for realistic curves in near linear time

Anne Driemel, Sariel Har-Peled, Carola Wenk

Research output: Contribution to journalArticlepeer-review


We present a simple and practical (1+ε)-approximation algorithm for the Fréchet distance between two polygonal curves in ℝ d. To analyze this algorithm we introduce a new realistic family of curves, c-packed curves, that is closed under simplification. We believe the notion of c-packed curves to be of independent interest. We show that our algorithm has near linear running time for c-packed polygonal curves, and similar results for other input models, such as low-density polygonal curves.

Original languageEnglish (US)
Pages (from-to)94-127
Number of pages34
JournalDiscrete and Computational Geometry
Issue number1
StatePublished - Jul 2012


  • Approximation algorithms
  • Frechet distance
  • Realistic input models

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


Dive into the research topics of 'Approximating the Fréchet distance for realistic curves in near linear time'. Together they form a unique fingerprint.

Cite this