Alves Akitaya, Hugo ;
Buchin, Maike ;
Ryvkin, Leonie ;
Urhausen, Jérôme
The kFréchet Distance: How to Walk Your Dog While Teleporting
Abstract
We introduce a new distance measure for comparing polygonal chains: the kFréchet distance. As the name implies, it is closely related to the wellstudied Fréchet distance but detects similarities between curves that resemble each other only piecewise. The parameter k denotes the number of subcurves into which we divide the input curves (thus we allow up to k1 "teleports" on each input curve). The kFréchet distance provides a nice transition between (weak) Fréchet distance and Hausdorff distance. However, we show that deciding this distance measure turns out to be NPhard, which is interesting since both (weak) Fréchet and Hausdorff distance are computable in polynomial time. Nevertheless, we give several possibilities to deal with the hardness of the kFréchet distance: besides a short exponentialtime algorithm for the general case, we give a polynomialtime algorithm for k=2, i.e., we ask that we subdivide our input curves into two subcurves each. We can also approximate the optimal k by factor 2. We then present a more intricate FPT algorithm using parameters k (the number of allowed subcurves) and z (the number of segments of one curve that intersect the epsilonneighborhood of a point on the other curve).
BibTeX  Entry
@InProceedings{alvesakitaya_et_al:LIPIcs:2019:11546,
author = {Hugo Alves Akitaya and Maike Buchin and Leonie Ryvkin and J{\'e}r{\^o}me Urhausen},
title = {{The kFr{\'e}chet Distance: How to Walk Your Dog While Teleporting}},
booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)},
pages = {50:150:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771306},
ISSN = {18688969},
year = {2019},
volume = {149},
editor = {Pinyan Lu and Guochuan Zhang},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2019/11546},
URN = {urn:nbn:de:0030drops115462},
doi = {10.4230/LIPIcs.ISAAC.2019.50},
annote = {Keywords: Measures, Fr{\'e}chet distance, Hardness, FPT}
}
28.11.2019
Keywords: 

Measures, Fréchet distance, Hardness, FPT 
Seminar: 

30th International Symposium on Algorithms and Computation (ISAAC 2019)

Issue date: 

2019 
Date of publication: 

28.11.2019 