Question
Is it possible to find an existing point's nearest neighbour within a logarithmic upper bound?
What I've tried
I have:
- the set of points $P$,
- a point $p$, where $p\in P$,
- a point $q$, where $q\notin P$,
- a Voronoi diagram, $V(P)$, of the points in $P$.
I know it's possible to query for a new point $q$'s nearest neighbour in $\mathcal{O}(\log{}n)$ time using $V(P)$ but is it possible to find the nearest neighbour of an existing point, such as $p$?
I've thought that if it wasn't possible, then I could delete the point $p$ in $V(P)$, assuming I could somehow create a dynamized Voronoi structure that allows for timely deletions (this paper notes that there is a way to insert points in constant time, so hopefully there's a Voronoi structure that allows deletions in logarithmic or less time), then search for the now non-existing point in logarithmic time. This would also solve my problem. Is there a dynamized Voronoi structure that allows deletions in $\mathcal{O}(\log n)$ time?