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

A. Driemel, S. Har-Peled

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

12 Citaten (Scopus)

Samenvatting

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(c^2 kn log^3 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 log^3 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.
Originele taal-2Engels
TitelProceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'12),17-19 january 2012, Kyoto, Japan
RedacteurenY. Rabani
UitgeverijSociety for Industrial and Applied Mathematics (SIAM)
Pagina's318-327
ISBN van geprinte versie978-1-61197-210-8
DOI's
StatusGepubliceerd - 2012
Extern gepubliceerdJa
Evenement23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012) - Westin Miyako, Kyoto, Japan
Duur: 17 jan 201219 jan 2012
Congresnummer: 23
http://www.siam.org/meetings/da12/

Congres

Congres23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012)
Verkorte titelSODA '12
LandJapan
StadKyoto
Periode17/01/1219/01/12
Ander23rd Annual ACM-SIAM Symposium on Discrete Algorithms
Internet adres

Vingerafdruk Duik in de onderzoeksthema's van 'Jaywalking your dog: Computing the Fréchet distance with shortcuts'. Samen vormen ze een unieke vingerafdruk.

Citeer dit