CGAL Delaunay Triangulation - 2nd closest neighbour

Question

Is there a more efficient way to get all vertices' 2nd closest neighbours in a (2D) delaunay triangulation than to compute for each the set of vertices reachable with at most two edge and select the 2nd-closest out of these?

Because even when we know at what maximum distance we will find it, range search seems to be slower, still.

Answer 1

To get the second nearest neighbor to a Delaunay vertex, you don't need to check all vertices that can be reach within two edge hops of the vertex. The second nearest neighbor to vertex v is either:

• a Delaunay neighbor of vertex v or
• a neighbor of the nearest neighbor to v.

Consider the red vertex in this image

and its second nearest neighbor. Look at the ball with diameter between the vertex in question and its second nearest neighbor. If the ball is empty, then it is a Delaunay neighbor of the vertex in question. If that ball contains any other vertices, it must contain only one which is the nearest neighbor. Moreover, we can imagine shrinking the ball until the nearest and second nearest neighbor are on the boundary. That ball will be empty ensuring the nearest and second nearest neighbors are Delaunay neighbors themselves.