Abstract

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 \in 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 \in P\) requires a substantial amount of space, we allow for approximating the distances. Given a parameter \(\varepsilon > 0\), we build an \(O(\frac{n}{\varepsilon}\log n)\) space data structure that can compute a \(1+\varepsilon\)-approximation of the distance between \(q\) and \(s\) in \(O(\frac{1}{\varepsilon^2}\log n)\) time. Building on this, we then obtain an \(O(\frac{n+m}{\varepsilon}\log n + \frac{m}{\varepsilon}\log m)\) space data structure that allows us to report a site \(s \in S\) so that the distance between query point \(q\) and \(s\) is at most \((1+\varepsilon)\)-times the distance between \(q\) and its true nearest neighbor in \(O(\frac{1}{\varepsilon^2}\log n + \frac{1}{\varepsilon}\log n \log m + \frac{1}{\varepsilon}\log^2 m)\) time. Our data structure supports updates in \(O(\frac{1}{\varepsilon^2}\log n + \frac{1}{\varepsilon}\log n \log m + \frac{1}{\varepsilon}\log^2 m)\) amortized time.

Corresponding Publications

Approximate Dynamic Nearest Neighbor Searching in a Polygonal Domain

Joost van der Laan, Frank Staals, Lorenzo Theunissen

Proc. 42th Annual Symposium on Computational Geometry, 2026

To Appear

Download Local Copy View Slides Export Citation

@inproceedings{dynApproxNNPolygonalDomain2026,
  author = {van der Laan, Joost and Staals, Frank and Theunissen, Lorenzo},
  title = {Approximate Dynamic Nearest Neighbor Searching in a Polygonal Domain},
  booktitle = {Proc. 42th Annual Symposium on Computational Geometry},
  year = {2026},
  location = {New Brunswick, NJ, USA},
  keywords = {data structure, polygonal domain, geodesic distance, shortest path},
  category = {geodesic},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  note = {To Appear},
}