Abstract
The Fréchet distance is a popular measure of dissimilarity for polygonal curves. It is defined as a minmax formulation that considers all directionpreserving continuous bijections of the two curves. Because of its susceptibility to noise, Driemel and HarPeled introduced the shortcut Fréchet distance in 2012, where one is allowed to take shortcuts along one of the curves, similar to the edit distance for sequences. We analyse the parameterized version of this problem, where the number of shortcuts is bounded by a parameter k. The corresponding decision problem can be stated as follows: Given two polygonal curves T and B of at most n vertices, a parameter k and a distance threshold δ, is it possible to introduce k shortcuts along B such that the Fréchet distance of the resulting curve and the curve T is at most δ? We study this problem for polygonal curves in the plane. We provide a complexity analysis for this problem with the following results: (i) assuming the exponentialtimehypothesis (ETH), there exists no algorithm with running time bounded by n^o(k); (ii) there exists a decision algorithm with running time in O(k n^{2k+2} log n). In contrast, we also show that efficient approximate decider algorithms are possible, even when k is large. We present a (3+ε)approximate decider algorithm with running time in O(k n² log² n) for fixed ε. In addition, we can show that, if k is a constant and the two curves are cpacked for some constant c, then the approximate decider algorithm runs in nearlinear time.
BibTeX  Entry
@InProceedings{conradi_et_al:LIPIcs.ICALP.2022.46,
author = {Conradi, Jacobus and Driemel, Anne},
title = {{On Computing the kShortcut Fr\'{e}chet Distance}},
booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
pages = {46:146:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772358},
ISSN = {18688969},
year = {2022},
volume = {229},
editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16387},
URN = {urn:nbn:de:0030drops163875},
doi = {10.4230/LIPIcs.ICALP.2022.46},
annote = {Keywords: Fr\'{e}chet distance, Partial similarity, Conditional lower bounds, Approximation algorithms}
}
Keywords: 

Fréchet distance, Partial similarity, Conditional lower bounds, Approximation algorithms 
Collection: 

49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) 
Issue Date: 

2022 
Date of publication: 

28.06.2022 