Approximating the Fréchet Distance for Realistic Curves in Near Linear Time

Abstract

We present simple and practical $(1+\eps)$-approximation algorithm for the Frechet distance between 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 curves, and show similar results for other input models.

To appear in SoCG 10

Cited by in corpus (4)

• Computing the Fréchet Distance with a Retractable Leash
• Lamb shift of non-degenerate energy level systems placed between two infinite parallel conducting plates
• Fréchet Distance Revisited and Extended
• An Algorithm for Comparing Similarity Between Two Trees