Buchin, Kevin ;
Fan, Chenglin ;
Löffler, Maarten ;
Popov, Aleksandr ;
Raichel, Benjamin ;
Roeloffzen, Marcel
Fréchet Distance for Uncertain Curves
Abstract
In this paper we study a wide range of variants for computing the (discrete and continuous) Fréchet distance between uncertain curves. We define an uncertain curve as a sequence of uncertainty regions, where each region is a disk, a line segment, or a set of points. A realisation of a curve is a polyline connecting one point from each region. Given an uncertain curve and a second (certain or uncertain) curve, we seek to compute the lower and upper bound Fréchet distance, which are the minimum and maximum Fréchet distance for any realisations of the curves.
We prove that both problems are NPhard for the continuous Fréchet distance, and the upper bound problem remains hard for the discrete Fréchet distance. In contrast, the lower bound discrete Fréchet distance can be computed in polynomial time using dynamic programming. Furthermore, we show that computing the expected discrete or continuous Fréchet distance is #Phard when the uncertainty regions are modelled as point sets or line segments.
On the positive side, we argue that in any constant dimension there is a FPTAS for the lower bound problem when Δ/δ is polynomially bounded, where δ is the Fréchet distance and Δ bounds the diameter of the regions. We then argue there is a nearlineartime 3approximation for the decision problem when the regions are convex and roughly δseparated. Finally, we study the setting with Sakoe  Chiba bands, restricting the alignment of the two curves, and give polynomialtime algorithms for upper bound and expected (discrete) Fréchet distance for pointsetmodelled uncertainty regions.
BibTeX  Entry
@InProceedings{buchin_et_al:LIPIcs:2020:12427,
author = {Kevin Buchin and Chenglin Fan and Maarten L{\"o}ffler and Aleksandr Popov and Benjamin Raichel and Marcel Roeloffzen},
title = {{Fr{\'e}chet Distance for Uncertain Curves}},
booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
pages = {20:120:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771382},
ISSN = {18688969},
year = {2020},
volume = {168},
editor = {Artur Czumaj and Anuj Dawar and Emanuela Merelli},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12427},
URN = {urn:nbn:de:0030drops124276},
doi = {10.4230/LIPIcs.ICALP.2020.20},
annote = {Keywords: Curves, Uncertainty, Fr{\'e}chet Distance, Hardness}
}
29.06.2020
Keywords: 

Curves, Uncertainty, Fréchet Distance, Hardness 
Seminar: 

47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Issue date: 

2020 
Date of publication: 

29.06.2020 