Home Bookmarks Papers Blog

Approximating the Frechet Distance for Realistic Curves in Near Linear Time

Anne Driemel, Sariel Har-Peled, and Carola Wenk.


We introduce a new realistic family of curves, which we call c-packed curves. Interestingly, this family is closed under simplification, a property that makes it especially useful. Next, we present the first near linear time approximation algorithm for the Frechet distance for polygonal c-packed curves in Rd. The algorithm also works in near linear time for low-density curves in the plane. In higher dimensions, one can approximate the Frechet distance of low-density curves in subquadratic time.


Postscript, PDF.
Slides.
Last modified: Tue Jan 26 04:59:05 CST 2010