Computing the Fréchet distance with shortcuts is NP-hard

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

13 Citaten (Scopus)
90 Downloads (Pure)


We study the shortcut Fréchet distance, a natural variant of the Fréchet distance, that allows us to take shortcuts from and to any point along one of the curves. The classic Fréchet distance is a bottle-neck distance measure and hence quite sensitive to outliers. The shortcut Fréchet distance allows us to cut across outliers and hence produces more meaningful results when dealing with real world data. Driemel and Har-Peled recently described approximation algorithms for the restricted case where shortcuts have to start and end at input vertices. We show that, in the general case, the problem of computing the shortcut Fréchet distance is NP-hard. This is the first hardness result for a variant of the Fréchet distance between two polygonal curves in the plane. We also present two algorithms for the decision problem: a 3-approximation algorithm for the general case and an exact algorithm for the vertex-restricted case. Both algorithms run in O(n3 log n) time.
Originele taal-2Engels
Titel30th ACM Symposium on Computational Geometry (SoCG, Kyoto, Japan, June 8-11, 2014)
Plaats van productieNew York NY
UitgeverijAssociation for Computing Machinery, Inc
ISBN van geprinte versie978-1-4503-2594-3
StatusGepubliceerd - 2014
Evenement30th Annual Symposium on Computational Geometry (SoCG 2014) - Kyoto, Japan
Duur: 8 jun 201411 jun 2014
Congresnummer: 30


Congres30th Annual Symposium on Computational Geometry (SoCG 2014)
Verkorte titelSoCG '14
Ander30th ACM Symposium on Computational Geometry

Vingerafdruk Duik in de onderzoeksthema's van 'Computing the Fréchet distance with shortcuts is NP-hard'. Samen vormen ze een unieke vingerafdruk.

Citeer dit