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?

  • 2
    $\begingroup$ 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. $\endgroup$ – 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.

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.