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

DOI10.1145/2582112.2582144MaRDI QIDQ4635561zbMATH OpenOpenAlexWikidataFDO

Authors Maike Buchin, Anne Driemel, Bettina Speckmann

Publication date 23 April 2018

Published in Proceedings of the thirtieth annual symposium on Computational geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1307.2097

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Abstract: We study the shortcut Fr'{e}chet distance, a natural variant of the Fr'{e}chet distance, that allows us to take shortcuts from and to any point along one of the curves. The classic Fr'echet distance is a bottle-neck distance measure and hence quite sensitive to outliers. The shortcut Fr'{e}chet distance allows us to cut across outliers and hence produces significantly 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'{e}chet distance is NP-hard. This is the first hardness result for a variant of the Fr'{e}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(n^3 log n) time.

Recommendations

• Jaywalking your dog: computing the Fréchet distance with shortcuts
• Jaywalking your dog: computing the Fréchet distance with shortcuts
• Computing the Fréchet distance with a retractable leash
• The Discrete and Semicontinuous Fréchet Distance with Shortcuts via Approximate Distance Counting and Selection
• The Discrete Fréchet Distance with Shortcuts via Approximate Distance Counting and Selection

Cited in

(12)

• On computing the \(k\)-shortcut Fréchet distance
• Fréchet Distance for Uncertain Curves
• Similarity of polygonal curves in the presence of outliers
• Computing the Fréchet distance between uncertain curves in one dimension
• How to walk your dog in the mountains with no magic leash
• Computing the Fréchet distance between uncertain curves in one dimension
• Computing the Fréchet gap distance
• Computing the Fréchet distance between polygons with holes
• SETH Says: Weak Fréchet Distance is Faster, but only if it is Continuous and in One Dimension
• Jaywalking your dog: computing the Fréchet distance with shortcuts
• Jaywalking your dog: computing the Fréchet distance with shortcuts
• scientific article; zbMATH DE number 7238975 (Why is no real title available?)

This page was built for publication: Computing the Fréchet distance with shortcuts is NP-hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4635561)