Computing the Fréchet distance with shortcuts is NP-hard
From MaRDI portal
Publication:4635561
DOI10.1145/2582112.2582144zbMath1395.68292arXiv1307.2097OpenAlexW2138661093MaRDI QIDQ4635561
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
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items
Fréchet Distance for Uncertain Curves, Similarity of polygonal curves in the presence of outliers, Computing the Fréchet gap distance, How to walk your dog in the mountains with no magic leash, Unnamed Item