2026-07-22T14:20:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16967 2024-03-06T10:58:50Z ddc:004 open_access

Efficient Fréchet Distance Queries for Segments Buchin, Maike van der Hoog, Ivor Ophelders, Tim Schlipf, Lena Silveira, Rodrigo I. Staals, Frank Computational Geometry Data Structures Fréchet distance 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Maike Buchin and Ivor van der Hoog and Tim Ophelders and Lena Schlipf and Rodrigo I. Silveira and Frank Staals 2022 Is Part Of LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2022.29 urn:nbn:de:0030-drops-169671 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.29 eng https://creativecommons.org/licenses/by/4.0/legalcode