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.
Journal version (SICOMP) PDF.
Last modified: Thu Oct 10 13:33:58 CDT 2013