TY - GEN

T1 - Jaywalking your dog - Computing the Fréchet distance with shortcuts

AU - Driemel, Anne

AU - Har-Peled, Sariel

PY - 2012

Y1 - 2012

N2 - The similarity of two polygonal curves can be measured using the Fréchet distance. We introduce the notion of a more robust Fréchet distance, where one is allowed to shortcut between vertices of one of the curves. This is a natural approach for handling noise, in particular batched outliers. We compute a constant factor approximation to the minimum Fréchet distance over all possible such shortcuts. Our algorithm runs in O (c2 kn log3 n) time if one is allowed to take at most k shortcuts and the input curves are c-packed. For the case where the number of shortcuts is unrestricted, we describe an algorithm which runs in O(c 2 n log3 n) time. 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 Fréchet distance between a subcurve and a line segment.

AB - The similarity of two polygonal curves can be measured using the Fréchet distance. We introduce the notion of a more robust Fréchet distance, where one is allowed to shortcut between vertices of one of the curves. This is a natural approach for handling noise, in particular batched outliers. We compute a constant factor approximation to the minimum Fréchet distance over all possible such shortcuts. Our algorithm runs in O (c2 kn log3 n) time if one is allowed to take at most k shortcuts and the input curves are c-packed. For the case where the number of shortcuts is unrestricted, we describe an algorithm which runs in O(c 2 n log3 n) time. 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 Fréchet distance between a subcurve and a line segment.

UR - http://www.scopus.com/inward/record.url?scp=84860186336&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84860186336&partnerID=8YFLogxK

U2 - 10.1137/1.9781611973099.30

DO - 10.1137/1.9781611973099.30

M3 - Conference contribution

AN - SCOPUS:84860186336

SN - 9781611972108

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 318

EP - 337

BT - Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012

PB - Association for Computing Machinery

T2 - 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012

Y2 - 17 January 2012 through 19 January 2012

ER -