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

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