# k-Closest pairs in Delaunay triangulation

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?

• There are then no points in the circle... – 今天春天 Jul 8 '16 at 6:56

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.