License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2022.29
URN: urn:nbn:de:0030-drops-169671
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16967/
Buchin, Maike ;
van der Hoog, Ivor ;
Ophelders, Tim ;
Schlipf, Lena ;
Silveira, Rodrigo I. ;
Staals, Frank
Efficient Fréchet Distance Queries for Segments
Abstract
We study the problem of constructing a data structure that can store a two-dimensional polygonal curve P, such that for any query segment ab one can efficiently compute the Fréchet distance between P and ab. First we present a data structure of size O(n log n) that can compute the Fréchet distance between P and a horizontal query segment ab in O(log n) time, where n is the number of vertices of P. In comparison to prior work, this significantly reduces the required space. We extend the type of queries allowed, as we allow a query to be a horizontal segment ab together with two points s, t ∈ P (not necessarily vertices), and ask for the Fréchet distance between ab and the curve of P in between s and t. Using O(nlog²n) storage, such queries take O(log³ n) time, simplifying and significantly improving previous results. We then generalize our results to query segments of arbitrary orientation. We present an O(nk^{3+ε}+n²) size data structure, where k ∈ [1,n] is a parameter the user can choose, and ε > 0 is an arbitrarily small constant, such that given any segment ab and two points s, t ∈ P we can compute the Fréchet distance between ab and the curve of P in between s and t in O((n/k)log²n+log⁴ n) time. This is the first result that allows efficient exact Fréchet distance queries for arbitrarily oriented segments.
We also present two applications of our data structure. First, we show that our data structure allows us to compute a local δ-simplification (with respect to the Fréchet distance) of a polygonal curve in O(n^{5/2+ε}) time, improving a previous O(n³) time algorithm. Second, we show that we can efficiently find a translation of an arbitrary query segment ab that minimizes the Fréchet distance with respect to a subcurve of P.
BibTeX - Entry
@InProceedings{buchin_et_al:LIPIcs.ESA.2022.29,
author = {Buchin, Maike and van der Hoog, Ivor and Ophelders, Tim and Schlipf, Lena and Silveira, Rodrigo I. and Staals, Frank},
title = {{Efficient Fr\'{e}chet Distance Queries for Segments}},
booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)},
pages = {29:1--29:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-247-1},
ISSN = {1868-8969},
year = {2022},
volume = {244},
editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16967},
URN = {urn:nbn:de:0030-drops-169671},
doi = {10.4230/LIPIcs.ESA.2022.29},
annote = {Keywords: Computational Geometry, Data Structures, Fr\'{e}chet distance}
}
|
Keywords: |
|
Computational Geometry, Data Structures, Fréchet distance |
|
Collection: |
|
30th Annual European Symposium on Algorithms (ESA 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
01.09.2022 |
