Finding the nearest neighbour of an existing 2d point in a set of points within $\mathcal{O}(\log{}n)$ time

Question

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?

Answer 1

If you have a voronoi diagram you have neighbour information of each $p$. You can use that to path search (using A* or even greedy depth first) to the 3 points that surround $q$. Then you can extract the closest from that.

If the voronoi is stored as a binary tree where each line divides the space into half-planes then it's just a dive into the search tree.