Approximating the Frechet Distance for Realistic Curves in Near Linear Time

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review


We present a simple and practical (1+\eps)-approximation algorithm for the Frechet distance between polygonal curves. 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 in Rd, and show similar results for other input models, such as low density.
Original languageEnglish
Title of host publicationProceedings of the 26th ACM Symposium on Computational Geometry, Snowbird, Utah, USA, June 13-16, 2010
EditorsJ. Snoeyink, M. de Berg, J.S.B. Mitchell, G. Rote, M. Teillaud
Number of pages10
Publication statusPublished - 13 Jun 2010


Dive into the research topics of 'Approximating the Frechet Distance for Realistic Curves in Near Linear Time'. Together they form a unique fingerprint.

Cite this