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

Anne Driemel, Sariel Har-Peled

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012
PublisherAssociation for Computing Machinery
Pages318-337
Number of pages20
ISBN (Print)9781611972108
DOIs
StatePublished - Jan 1 2012
Event23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012 - Kyoto, Japan
Duration: Jan 17 2012Jan 19 2012

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012
CountryJapan
CityKyoto
Period1/17/121/19/12

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Jaywalking your dog - Computing the Fréchet distance with shortcuts'. Together they form a unique fingerprint.

  • Cite this

    Driemel, A., & Har-Peled, S. (2012). Jaywalking your dog - Computing the Fréchet distance with shortcuts. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012 (pp. 318-337). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms). Association for Computing Machinery. https://doi.org/10.1137/1.9781611973099.30