Approximating the Fréchet distance for realistic curves in near linear time
Anne Driemel, Sariel Har-Peled, Carola Wenk · 2010
We present a simple and practical (1+ε)-approximation algorithm for the Fréchet 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, and show similar results for other input models, such as low density.