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

M. Buchin, A. Driemel, B. Speckmann

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

20 Citations (Scopus)
219 Downloads (Pure)

Abstract

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.
Original languageEnglish
Title of host publication30th ACM Symposium on Computational Geometry (SoCG, Kyoto, Japan, June 8-11, 2014)
Place of PublicationNew York NY
PublisherAssociation for Computing Machinery, Inc
Pages367-376
ISBN (Print)978-1-4503-2594-3
DOIs
Publication statusPublished - 2014
Event30th Annual Symposium on Computational Geometry (SoCG 2014) - Kyoto, Japan
Duration: 8 Jun 201411 Jun 2014
Conference number: 30

Conference

Conference30th Annual Symposium on Computational Geometry (SoCG 2014)
Abbreviated titleSoCG '14
Country/TerritoryJapan
CityKyoto
Period8/06/1411/06/14

Fingerprint

Dive into the research topics of 'Computing the Fréchet distance with shortcuts is NP-hard'. Together they form a unique fingerprint.

Cite this