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

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?

• You can precompute the answer by (essentially) going over all edges in the Voronoi diagram (there are $O(n)$ of them since the graph is planar) and store it in an array. Then you can answer your query in constant time. – Yuval Filmus Jun 29 '17 at 15:59

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.