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 language | English |
---|---|
Title of host publication | 30th ACM Symposium on Computational Geometry (SoCG, Kyoto, Japan, June 8-11, 2014) |
Place of Publication | New York NY |
Publisher | Association for Computing Machinery, Inc |
Pages | 367-376 |
ISBN (Print) | 978-1-4503-2594-3 |
DOIs | |
Publication status | Published - 2014 |
Event | 30th Annual Symposium on Computational Geometry (SoCG 2014) - Kyoto, Japan Duration: 8 Jun 2014 → 11 Jun 2014 Conference number: 30 |
Conference
Conference | 30th Annual Symposium on Computational Geometry (SoCG 2014) |
---|---|
Abbreviated title | SoCG '14 |
Country/Territory | Japan |
City | Kyoto |
Period | 8/06/14 → 11/06/14 |