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

A. Driemel, S. Har-Peled, C. Wenk

Research output: Contribution to journalArticleAcademicpeer-review

50 Citations (Scopus)
46 Downloads (Pure)

Abstract

We present a simple and practical (1+e)-approximation algorithm for the Fréchet distance between two polygonal curves in R^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
Pages (from-to)94-127
JournalDiscrete and Computational Geometry
Volume48
Issue number1
DOIs
Publication statusPublished - 2012
Externally publishedYes

Fingerprint 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