2026-07-21T19:38:41Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24914 2026-02-09T08:01:58Z ddc:004 open_access

A Dimension-Reducing Fréchet Simplification Oracle Aronov, Boris Farhana, Tsuri Katz, Matthew J. Ramesh, Indu Computational geometry discrete Fréchet distance curve simplification oracle restricted minimum enclosing disk queries Let P be a polygonal curve with n vertices in the plane. We construct a data structure of size O(n log n) suited for simplification queries of the following kind. Given a query line 𝓁 and an integer k ≥ 1, find a curve Q on 𝓁 with at most k vertices that minimizes the discrete Fréchet distance to P, among all such curves. Using our data structure, a query can be handled in O(k² log³ n + k log⁴n) time. More generally, a geometric tree T on n vertices in the plane can be preprocessed into a near-linear-size structure so that, given a pair u, v of its vertices, a line 𝓁, and an integer k ≥ 1, one can find a curve Q on 𝓁 with at most k vertices that minimizes the discrete Fréchet distance to the path from u to v in T, in time O(k² polylog n). For the general dimension-reduction problem, where P is a curve in ℝ^d (d ≥ 3), 0 < ε₀ < 1 is a real parameter, and a query specifies a g-flat h (1 ≤ g ≤ d-1) and an integer k ≥ 1, we construct a data structure of size O(nlog n + f(ε₀) n), where f(ε₀) = (1+1/ε₀)^{(d-1)/2}, that allows us to find a curve Q on h with at most k vertices, whose discrete Fréchet distance to P is at most 1+ε₀ times the distance of Q^* to P, where Q^* is such a curve that minimizes the distance to P. The query handling time is O(f(ε₀) k² log² n). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Boris Aronov and Tsuri Farhana and Matthew J. Katz and Indu Ramesh 2025 Is Part Of LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2025.6 urn:nbn:de:0030-drops-249149 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.6 eng https://creativecommons.org/licenses/by/4.0/legalcode