Approximate Dynamic Nearest Neighbor Searching in a Polygonal Domain

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 $\epsilon >0$, we build an $O(\frac{n}{\epsilon }\log n)$ space data structure that can compute a $1+\epsilon$-approximation of the distance between $q$ and $s$ in $O(\frac{1}{{\epsilon }^2}\log n)$ time. Building on this, we then obtain an $O(\frac{n+m}{\epsilon }\log n+\frac{m}{\epsilon }\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+\epsilon )$-times the distance between $q$ and its true nearest neighbor in $O(\frac{1}{{\epsilon }^2}\log n+\frac{1}{\epsilon }\log n\log m+\frac{1}{\epsilon }{\log }^{2}m)$ time. Our data structure supports updates in $O(\frac{1}{{\epsilon }^2}\log n+\frac{1}{\epsilon }\log n\log m+\frac{1}{\epsilon }{\log }^{2}m)$ amortized time.

Full version of our SoCG 2026 paper