Home Bookmarks Papers Blog

Jaywalking your Dog -- The Frechet Distance with Shortcuts for Realistic Curves with Noise

Anne Driemel and Sariel Har-Peled.


We present a near linear time algorithm for approximating the Frechet distance between two polygonal curves up to a factor of (3 + eps), when one is allowed to shortcut one of the curves a specified number of times. This is a natural approach for handling noise, missing parts or outliers. To facilitate the new algorithm we develop several new data-structures, which we believe to be of independent interest: (i) for range reporting on a curve, and (ii) for preprocessing a curve to answer queries for the Frechet distance between a subcurve and a line segment. We assume c-packedness as an input model for the problems considered.
PDF.
Journal version (SICOMP) PDF.
Last modified: Thu Oct 10 13:33:58 CDT 2013