2026-07-20T11:45:59Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18092 2024-03-06T11:00:59Z ddc:004 open_access

Approximate Nearest Neighbor for Polygonal Curves Under Fréchet Distance Cheng, Siu-Wing Huang, Haoqiang Polygonal curves Fréchet distance approximate nearest neighbor We propose κ-approximate nearest neighbor (ANN) data structures for n polygonal curves under the Fréchet distance in ℝ^d, where κ ∈ {1+ε,3+ε} and d ≥ 2. We assume that every input curve has at most m vertices, every query curve has at most k vertices, k ≪ m, and k is given for preprocessing. The query times are Õ(k(mn)^{0.5+ε}/ε^d+ k(d/ε)^O(dk)) for (1+ε)-ANN and Õ(k(mn)^{0.5+ε}/ε^d) for (3+ε)-ANN. The space and expected preprocessing time are Õ(k(mnd^d/ε^d)^O(k+1/ε²)) in both cases. In two and three dimensions, we improve the query times to O(1/ε)^O(k) ⋅ Õ(k) for (1+ε)-ANN and Õ(k) for (3+ε)-ANN. The space and expected preprocessing time improve to O(mn/ε)^O(k) ⋅ Õ(k) in both cases. For ease of presentation, we treat factors in our bounds that depend purely on d as O(1). The hidden polylog factors in the big-Õ notation have powers dependent on d. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Siu-Wing Cheng and Haoqiang Huang 2023 Is Part Of LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2023.40 urn:nbn:de:0030-drops-180929 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.40 eng https://creativecommons.org/licenses/by/4.0/legalcode