2026-07-20T04:47:59Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25876 2026-06-23T13:00:02Z ddc:004 open_access

Approximate Dynamic Nearest Neighbor Searching in a Polygonal Domain van der Laan, Joost Staals, Frank Theunissen, Lorenzo dynamic data structure nearest neighbor search polygonal domain We present efficient data structures for approximate nearest neighbor searching and approximate 2-point shortest path queries in a two-dimensional polygonal domain P with n vertices. Our goal is to store a dynamic set of m point sites S in P so that we can efficiently find a site s ∈ S closest to an arbitrary query point q. We will allow both insertions and deletions in the set of sites S. However, as even just computing the distance between an arbitrary pair of points q,s ∈ P requires a substantial amount of space, we allow for approximating the distances. Given a parameter ε > 0, we build an O(n/(ε)log n) space data structure that can compute a 1+ε-approximation of the distance between q and s in O((1/ε²)log n) time. Building on this, we then obtain an O((n+m)/ε log n + m/ε log m) space data structure that allows us to report a site s ∈ S so that the distance between query point q and s is at most (1+ε)-times the distance between q and its true nearest neighbor in O((1/ε²)log n + 1/(ε)log n log m + (1/ε)log² m) time. Our data structure supports updates in O((1/ε²)log n + (1/ε)log n log m + (1/ε)log² m) amortized time. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Joost van der Laan and Frank Staals and Lorenzo Theunissen 2026 Is Part Of LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2026.69 urn:nbn:de:0030-drops-258769 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.69 eng https://creativecommons.org/licenses/by/4.0/legalcode