Computing the Fréchet Distance Between Uncertain Curves in One Dimension

Kevin Buchin; Maarten Löffler; Tim Ophelders; Aleksandr Popov; Jérôme Urhausen; Kevin Verbeek

doi:10.1016/j.comgeo.2022.101923

Computing the Fréchet Distance Between Uncertain Curves in One Dimension

Kevin Buchin
, Maarten Löffler
, Tim Ophelders
, Aleksandr Popov (Corresponding author)
, Jérôme Urhausen
, Kevin Verbeek

Algorithms

Research output: Contribution to journal › Article › Academic › peer-review

9 Citations (Scopus)

362 Downloads (Pure)

Abstract

We consider the problem of computing the Fréchet distance between two curves for which the exact locations of the vertices are unknown. Each vertex may be placed in a given uncertainty region for that vertex, and the objective is to place vertices so as to minimise the Fréchet distance. This problem was recently shown to be NP-hard in 2D, and it is unclear how to compute an optimal vertex placement at all.

We present the first general algorithmic framework for this problem. We prove that it results in a polynomial-time algorithm for curves in 1D with intervals as uncertainty regions. In contrast, we show that the problem is NP-hard in 1D in the case that vertices are placed to maximise the Fréchet distance.

We also study the weak Fréchet distance between uncertain curves. While finding the optimal placement of vertices seems more difficult than the regular Fréchet distance—and indeed we can easily prove that the problem is NP-hard in 2D—the optimal placement of vertices in 1D can be computed in polynomial time. Finally, we investigate the discrete weak Fréchet distance, for which, somewhat surprisingly, the problem is NP-hard already in 1D.

Original language	English
Article number	101923
Number of pages	21
Journal	Computational Geometry
Volume	109
DOIs	https://doi.org/10.1016/j.comgeo.2022.101923
Publication status	Published - 1 Feb 2023

Funding

Partially supported by the Dutch Research Council (NWO) under project no. 614.001.504.Supported by the Dutch Research Council (NWO) under project no. 612.001.801.Supported by the Dutch Research Council (NWO) under project no. 612.001.651.

Funders	Funder number
Nederlandse Organisatie voor Wetenschappelijk Onderzoek	612.001.651, 614.001.504, 612.001.801

Keywords

curves
uncertainty
Fréchet distance
hardness
weak Fréchet distance
Uncertainty
Weak Fréchet distance
Hardness
Curves

Access to Document

10.1016/j.comgeo.2022.101923Licence: CC BY

pdfFinal published version, 644 KBLicence: CC BY

Cite this

@article{23f9db6320a94bf59ee169021d57b707,

title = "Computing the Fr{\'e}chet Distance Between Uncertain Curves in One Dimension",

abstract = "We consider the problem of computing the Fr{\'e}chet distance between two curves for which the exact locations of the vertices are unknown. Each vertex may be placed in a given uncertainty region for that vertex, and the objective is to place vertices so as to minimise the Fr{\'e}chet distance. This problem was recently shown to be NP-hard in 2D, and it is unclear how to compute an optimal vertex placement at all. We present the first general algorithmic framework for this problem. We prove that it results in a polynomial-time algorithm for curves in 1D with intervals as uncertainty regions. In contrast, we show that the problem is NP-hard in 1D in the case that vertices are placed to maximise the Fr{\'e}chet distance. We also study the weak Fr{\'e}chet distance between uncertain curves. While finding the optimal placement of vertices seems more difficult than the regular Fr{\'e}chet distance{\textemdash}and indeed we can easily prove that the problem is NP-hard in 2D{\textemdash}the optimal placement of vertices in 1D can be computed in polynomial time. Finally, we investigate the discrete weak Fr{\'e}chet distance, for which, somewhat surprisingly, the problem is NP-hard already in 1D.",

keywords = "curves, uncertainty, Fr{\'e}chet distance, hardness, weak Fr{\'e}chet distance, Uncertainty, Weak Fr{\'e}chet distance, Hardness, Curves",

author = "Kevin Buchin and Maarten L{\"o}ffler and Tim Ophelders and Aleksandr Popov and J{\'e}r{\^o}me Urhausen and Kevin Verbeek",

year = "2023",

month = feb,

day = "1",

doi = "10.1016/j.comgeo.2022.101923",

language = "English",

volume = "109",

journal = "Computational Geometry",

issn = "0925-7721",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Computing the Fréchet Distance Between Uncertain Curves in One Dimension

AU - Buchin, Kevin

AU - Löffler, Maarten

AU - Ophelders, Tim

AU - Popov, Aleksandr

AU - Urhausen, Jérôme

AU - Verbeek, Kevin

PY - 2023/2/1

Y1 - 2023/2/1

N2 - We consider the problem of computing the Fréchet distance between two curves for which the exact locations of the vertices are unknown. Each vertex may be placed in a given uncertainty region for that vertex, and the objective is to place vertices so as to minimise the Fréchet distance. This problem was recently shown to be NP-hard in 2D, and it is unclear how to compute an optimal vertex placement at all. We present the first general algorithmic framework for this problem. We prove that it results in a polynomial-time algorithm for curves in 1D with intervals as uncertainty regions. In contrast, we show that the problem is NP-hard in 1D in the case that vertices are placed to maximise the Fréchet distance. We also study the weak Fréchet distance between uncertain curves. While finding the optimal placement of vertices seems more difficult than the regular Fréchet distance—and indeed we can easily prove that the problem is NP-hard in 2D—the optimal placement of vertices in 1D can be computed in polynomial time. Finally, we investigate the discrete weak Fréchet distance, for which, somewhat surprisingly, the problem is NP-hard already in 1D.

AB - We consider the problem of computing the Fréchet distance between two curves for which the exact locations of the vertices are unknown. Each vertex may be placed in a given uncertainty region for that vertex, and the objective is to place vertices so as to minimise the Fréchet distance. This problem was recently shown to be NP-hard in 2D, and it is unclear how to compute an optimal vertex placement at all. We present the first general algorithmic framework for this problem. We prove that it results in a polynomial-time algorithm for curves in 1D with intervals as uncertainty regions. In contrast, we show that the problem is NP-hard in 1D in the case that vertices are placed to maximise the Fréchet distance. We also study the weak Fréchet distance between uncertain curves. While finding the optimal placement of vertices seems more difficult than the regular Fréchet distance—and indeed we can easily prove that the problem is NP-hard in 2D—the optimal placement of vertices in 1D can be computed in polynomial time. Finally, we investigate the discrete weak Fréchet distance, for which, somewhat surprisingly, the problem is NP-hard already in 1D.

KW - curves

KW - uncertainty

KW - Fréchet distance

KW - hardness

KW - weak Fréchet distance

KW - Uncertainty

KW - Weak Fréchet distance

KW - Hardness

KW - Curves

UR - https://www.scopus.com/pages/publications/85136541329

U2 - 10.1016/j.comgeo.2022.101923

DO - 10.1016/j.comgeo.2022.101923

M3 - Article

SN - 0925-7721

VL - 109

JO - Computational Geometry

JF - Computational Geometry

M1 - 101923

ER -

Computing the Fréchet Distance Between Uncertain Curves in One Dimension

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Algorithms for Imprecise Trajectories

Computing the Fréchet Distance Between Uncertain Curves in One Dimension

Cite this