Fréchet Distance for Uncertain Curves

Kevin Buchin, Chenglin Fan, Maarten Löffler, Aleksandr Popov, Benjamin Raichel, Marcel Roeloffzen

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review


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 NP-hard 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 #P-hard 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 near-linear-time 3-approximation 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 polynomial-time algorithms for upper bound and expected (discrete) Fréchet distance for point-set-modelled uncertainty regions.
Originele taal-2Engels
Titel47th International Colloquium on Automata, Languages, and Programming, ICALP 2020
SubtitelICALP 2020
RedacteurenArtur Czumaj, Anuj Dawar, Emanuela Merelli
Plaats van productieDagstuhl, Germany
UitgeverijSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Aantal pagina's20
ISBN van elektronische versie978-3-95977-138-2
StatusGepubliceerd - 29 jun 2020
Evenement47th International Colloquium on Automata, Languages, and Programming - Online, Saarbrücken, Duitsland
Duur: 8 jul 202011 jul 2020

Publicatie series

NaamLeibniz International Proceedings in Informatics (LIPIcs)
UitgeverijSchloss Dagstuhl–Leibniz-Zentrum für Informatik
ISSN van elektronische versie1868-8969


Congres47th International Colloquium on Automata, Languages, and Programming
Verkorte titelICALP 2020
Internet adres

Vingerafdruk Duik in de onderzoeksthema's van 'Fréchet Distance for Uncertain Curves'. Samen vormen ze een unieke vingerafdruk.

Citeer dit