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

DOI10.1145/2582112.2582144zbMATH Open1395.68292arXiv1307.2097OpenAlexW2138661093WikidataQ130995449 ScholiaQ130995449MaRDI QIDQ4635561FDOQ4635561

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)

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.

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)

Cited In (6)

• Fréchet Distance for Uncertain Curves
• Similarity of polygonal curves in the presence of outliers
• How to walk your dog in the mountains with no magic leash
• Computing the Fréchet gap distance
• SETH Says: Weak Fréchet Distance is Faster, but only if it is Continuous and in One Dimension
• Title not available (Why is that?)

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)