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.1007/978-3-030-83508-8_18

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

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 give a polynomial-time algorithm for 1D curves 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 for 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
Title of host publication	Algorithms and Data Structures
Subtitle of host publication	17th International Symposium, WADS 2021, Virtual Event, August 9–11, 2021, Proceedings
Editors	Anna Lubiw, Mohammad Salavatipour, Meng He
Place of Publication	Cham
Publisher	Springer Nature
Pages	243–257
Number of pages	15
ISBN (Electronic)	978-3-030-83508-8
ISBN (Print)	978-3-030-83507-1
DOIs	https://doi.org/10.1007/978-3-030-83508-8_18
Publication status	Published - 31 Jul 2021
Event	17th Algorithms and Data Structures Symposium - Online, Halifax, Canada Duration: 9 Aug 2021 → 11 Aug 2021 Conference number: 17 https://projects.cs.dal.ca/wads2021/

Publication series

Name	Lecture Notes in Computer Science (LNCS)
Volume	12808
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Name	Theoretical Computer Science and General Issues (LNTCS)
Volume	12808
ISSN (Print)	2512-2010
ISSN (Electronic)	2512-2029

Conference

Conference	17th Algorithms and Data Structures Symposium
Abbreviated title	WADS 2021
Country/Territory	Canada
City	Halifax
Period	9/08/21 → 11/08/21
Internet address	https://projects.cs.dal.ca/wads2021/

Funding

Acknowledgements. Research on the topic of this paper was initiated at the 5th Workshop on Applied Geometric Algorithms (AGA 2020) in Langbroek, Netherlands. Maarten Löﬄer is partially supported by the Dutch Research Council (NWO) under project no. 614.001.504 and no. 628.011.005. Aleksandr Popov is supported by the Dutch Research Council (NWO) under project no. 612.001.801. Jérôme Urhausen is supported by the Dutch Research Council (NWO) under project no. 612.001.651.

Keywords

curves
uncertainty
Fréchet distance
1D
hardness
weak Fréchet distance

Access to Document

10.1007/978-3-030-83508-8_18

pdfFinal published version, 453 KBLicence: TAVERNE

https://arxiv.org/abs/2105.09922Licence: CC BY

Cite this

Buchin, K., Löffler, M., Ophelders, T., Popov, A., Urhausen, J., & Verbeek, K. (2021). Computing the Fréchet Distance Between Uncertain Curves in One Dimension. In A. Lubiw, M. Salavatipour, & M. He (Eds.), Algorithms and Data Structures: 17th International Symposium, WADS 2021, Virtual Event, August 9–11, 2021, Proceedings (pp. 243–257). (Lecture Notes in Computer Science (LNCS); Vol. 12808), (Theoretical Computer Science and General Issues (LNTCS); Vol. 12808). Springer Nature. https://doi.org/10.1007/978-3-030-83508-8_18

Buchin, Kevin ; Löffler, Maarten ; Ophelders, Tim et al. / Computing the Fréchet Distance Between Uncertain Curves in One Dimension. Algorithms and Data Structures: 17th International Symposium, WADS 2021, Virtual Event, August 9–11, 2021, Proceedings. editor / Anna Lubiw ; Mohammad Salavatipour ; Meng He. Cham : Springer Nature, 2021. pp. 243–257 (Lecture Notes in Computer Science (LNCS)). (Theoretical Computer Science and General Issues (LNTCS)).

@inproceedings{21fcd50f4ac54a83a3cc1f50d3909570,

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 give a polynomial-time algorithm for 1D curves 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 for 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, 1D, hardness, weak Fr{\'e}chet distance",

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 = "2021",

month = jul,

day = "31",

doi = "10.1007/978-3-030-83508-8\_18",

language = "English",

isbn = "978-3-030-83507-1",

series = "Lecture Notes in Computer Science (LNCS)",

publisher = "Springer Nature",

pages = "243–257",

editor = "Anna Lubiw and Mohammad Salavatipour and Meng He",

booktitle = "Algorithms and Data Structures",

address = "Singapore",

note = "17th Algorithms and Data Structures Symposium, WADS 2021 ; Conference date: 09-08-2021 Through 11-08-2021",

url = "https://projects.cs.dal.ca/wads2021/",

}

Buchin, K, Löffler, M, Ophelders, T, Popov, A, Urhausen, J & Verbeek, K 2021, Computing the Fréchet Distance Between Uncertain Curves in One Dimension. in A Lubiw, M Salavatipour & M He (eds), Algorithms and Data Structures: 17th International Symposium, WADS 2021, Virtual Event, August 9–11, 2021, Proceedings. Lecture Notes in Computer Science (LNCS), vol. 12808, Theoretical Computer Science and General Issues (LNTCS), vol. 12808, Springer Nature, Cham, pp. 243–257, 17th Algorithms and Data Structures Symposium, Halifax, Nova Scotia, Canada, 9/08/21. https://doi.org/10.1007/978-3-030-83508-8_18

Computing the Fréchet Distance Between Uncertain Curves in One Dimension. / Buchin, Kevin; Löffler, Maarten; Ophelders, Tim et al.
Algorithms and Data Structures: 17th International Symposium, WADS 2021, Virtual Event, August 9–11, 2021, Proceedings. ed. / Anna Lubiw; Mohammad Salavatipour; Meng He. Cham: Springer Nature, 2021. p. 243–257 (Lecture Notes in Computer Science (LNCS); Vol. 12808), (Theoretical Computer Science and General Issues (LNTCS); Vol. 12808).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

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

N1 - Conference code: 17

PY - 2021/7/31

Y1 - 2021/7/31

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 give a polynomial-time algorithm for 1D curves 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 for 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 give a polynomial-time algorithm for 1D curves 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 for 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 - 1D

KW - hardness

KW - weak Fréchet distance

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

U2 - 10.1007/978-3-030-83508-8_18

DO - 10.1007/978-3-030-83508-8_18

M3 - Conference contribution

SN - 978-3-030-83507-1

T3 - Lecture Notes in Computer Science (LNCS)

SP - 243

EP - 257

BT - Algorithms and Data Structures

A2 - Lubiw, Anna

A2 - Salavatipour, Mohammad

A2 - He, Meng

PB - Springer Nature

CY - Cham

T2 - 17th Algorithms and Data Structures Symposium

Y2 - 9 August 2021 through 11 August 2021

ER -

Buchin K, Löffler M, Ophelders T, Popov A, Urhausen J, Verbeek K. Computing the Fréchet Distance Between Uncertain Curves in One Dimension. In Lubiw A, Salavatipour M, He M, editors, Algorithms and Data Structures: 17th International Symposium, WADS 2021, Virtual Event, August 9–11, 2021, Proceedings. Cham: Springer Nature. 2021. p. 243–257. (Lecture Notes in Computer Science (LNCS)). (Theoretical Computer Science and General Issues (LNTCS)). Epub 2021 May 20. doi: 10.1007/978-3-030-83508-8_18

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

Abstract

Publication series

Conference

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