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

Onderzoeksoutput: Bijdrage aan tijdschrift › Tijdschriftartikel › Academic › peer review

8 Citaten (Scopus)

190 Downloads (Pure)

Samenvatting

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.

Originele taal-2	Engels
Artikelnummer	101923
Aantal pagina's	21
Tijdschrift	Computational Geometry
Volume	109
DOI's	https://doi.org/10.1016/j.comgeo.2022.101923
Status	Gepubliceerd - 1 feb. 2023

Financiering

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.

Financiers	Financiernummer
Nederlandse Organisatie voor Wetenschappelijk Onderzoek	612.001.651, 614.001.504, 612.001.801

Toegang tot document

10.1016/j.comgeo.2022.101923Licentie: CC BY

pdfDefinitieve gepubliceerde versie, 644 KBLicentie: CC BY

Andere bestanden en links

Link naar publicatie in Scopus

8 Citaties
1 Conferentiebijdrage
1 Dissertatie 1 (Onderzoek TU/e / Promotie TU/e)

Algorithms for Imprecise Trajectories
Popov, A. A., 12 okt. 2023, Eindhoven: Eindhoven University of Technology. 259 blz.
Onderzoeksoutput: Scriptie › Dissertatie 1 (Onderzoek TU/e / Promotie TU/e)

Open Access
Bestand
Computing the Fréchet Distance Between Uncertain Curves in One Dimension
Buchin, K., Löffler, M., Ophelders, T., Popov, A., Urhausen, J. & Verbeek, K., 11 aug. 2021, Algorithms and Data Structures: 17th International Symposium, WADS 2021, Virtual Event, August 9–11, 2021, Proceedings. Lubiw, A. & Salavatipour, M. (uitgave). Cham, Switzerland: Springer Nature, blz. 243–257 15 blz. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 12808 LNCS).
Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

Citeer dit

@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—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{\'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 - http://www.scopus.com/inward/record.url?scp=85136541329&partnerID=8YFLogxK

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

Samenvatting

Financiering

Toegang tot document

Andere bestanden en links

Vingerafdruk

Onderzoekersoutput

Algorithms for Imprecise Trajectories

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

Citeer dit