CGAL users discussion list

[Joshua A Levine <>]

This is likely not the fastest way, but it's a correct "brute force" one:

A Delaunay triangulation possesses the property such that for any point p, 
there is always an edge from p to it's the nearest neighbor q.

So if you want to compute the set of reverse neighbors for a point q, you 
need only to look at all points p that have edges to q.  Collect the adjacent 
vertices to a point q, compute the nearest neighbor to each of them, and save 
the set of them that have q as their nearest neighbor.  The positive of this 
is that it's a local search for any point q.  The negative is that you have 
to compute the nearest neighbor for every adjacent point to q.  If your 
Delaunay triangulation is static you could precompute these though.

Pseudocode:

list<Vert> RevNearNeighbors(Vert q) {

 list<Vert> rnn = {}.

 For each vertex p adjacent to q in Delaunay:
   Compute the nearest neighbor r of p.
   If r == q,
     rnn.insert(p).
   --
 --

 return rnn.
}

Häberling Armin wrote:
> Hi,
>
> I'd like to compute the reverse nearest neighbour for a delaunay
> triangulation. I.e. for a given query point q I want to find all
> vertices in the triangulation that have q as their nearest neighbour.
>
>
> I found on the web a lot about alogritms for nearest neighbour
> queries, but nothing about the reverse nearest neighbour. Has anyone
> done something like this before or does know a fast algorithm for
> this.
>
> Thanks in advance
>
> Armin