k-Closest pairs in Delaunay triangulation

Question

Assume there is a set of points $S$ in $\mathbb{R^2}$. In this set of points there is a pair of points which are the nearest neighbors, the second-nearest neighbors and the third-nearest neighbors.

I want to show that the pair of points which represent:

1. the nearest neighbors,
2. the second nearest neighbors,
3. the third nearest neigbors

are also an edge in the corresponding Delaunay Triangulation.

Any hints on how to prove this?

Answer 1

This article [1] shows that this is not always true for the second-nearest neighbour and forth. It shows that it is indeed the case for the (1st) nearest neighbour, and it's trivial, given the theorem that claims that if the circle defined by 2 points (as its diameter) is empty of other points then these points lie on an edge of the delaunay triangulation.

I didn't find a proper proof for that, and it is definitely not true for the opposite direction (not every edge of the DT defines an empty circle), but I have an idea of why this is true -

Let the points a,b define a circle Cab, having a-b as its diameter, empty of other points. The circle is empty of points, but cannot be empty of edges (the line connecting any pair of points must either be an edge or intersect an edge (by convexity of the map, and the fact that there are no diagonals in triangles). Suppose a-b is not an edge of the DT, then it intersects an edge c-d, with both c and d out of Cab, that is part of a triangle c-d-e that either has w.l.o.g e=a, or e != a and is also outside of Cab, but this doesn't matter. Anyway, the angles $\angle acb$ and $\angle adb$ have to be both sharp, as they are supported by the diameter of Cab, a-b, and lie outside of it, so this means $\angle cad + \angle cbd > 180^{\circ}$ (sum of angles in tetragon is 360), but as c-d is a chord in Ccde, so this means that at least one of the points a,b lies in Ccde, so c-d-e is not a legal delaunay triangle - contradiction.

Hope this hand waving is sufficient for your understanding.

1. All closest neighbors are proper Delaunay edges generalized, and its application to parallel algorithms by Arne Maus and Jon Moen Drange (2010)