2026-08-07T13:42:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22184 2024-12-04T06:53:45Z ddc:004 open_access

Data Structures for Approximate Fréchet Distance for Realistic Curves van der Hoog, Ivor Rotenberg, Eva Wong, Sampson Fréchet distance data structures approximation algorithms The Fréchet distance is a popular distance measure between curves P and Q. Conditional lower bounds prohibit (1+ε)-approximate Fréchet distance computations in strongly subquadratic time, even when preprocessing P using any polynomial amount of time and space. As a consequence, the Fréchet distance has been studied under realistic input assumptions, for example, assuming both curves are c-packed. In this paper, we study c-packed curves in Euclidean space ℝ^d and in general geodesic metrics 𝒳. In ℝ^d, we provide a nearly-linear time static algorithm for computing the (1+ε)-approximate continuous Fréchet distance between c-packed curves. Our algorithm has a linear dependence on the dimension d, as opposed to previous algorithms which have an exponential dependence on d. In general geodesic metric spaces X, little was previously known. We provide the first data structure, and thereby the first algorithm, under this model. Given a c-packed input curve P with n vertices, we preprocess it in O(n log n) time, so that given a query containing a constant ε and a curve Q with m vertices, we can return a (1+ε)-approximation of the discrete Fréchet distance between P and Q in time polylogarithmic in n and linear in m, 1/ε, and the realism parameter c. Finally, we show several extensions to our data structure; to support dynamic extend/truncate updates on P, to answer map matching queries, and to answer Hausdorff distance queries. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ivor van der Hoog and Eva Rotenberg and Sampson Wong 2024 Is Part Of LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2024.56 urn:nbn:de:0030-drops-221846 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.56 eng https://creativecommons.org/licenses/by/4.0/legalcode