Closest Pair of Points Problem - Planar Case

Planar Case

The problem can be solved in O(n log n) time using the recursive divide and conquer approach, e.g., as follows:

1. Sort points according to their x-coordinates.
2. Split the set of points into two equal-sized subsets by a vertical line x=x_mid.
3. Solve the problem recursively in the left and right subsets. This yields the left-side and right-side minimum distances d_Lmin and d_Rmin, respectively.
4. Find the minimal distance d_LRmin among the pair of points in which one point lies on the left of the dividing vertical and the second point lies to the right.
5. The final answer is the minimum among d_Lmin, d_Rmin, and d_LRmin.

It turns out that step 4 may be accomplished in linear time. Again, a naive approach would require the calculation of distances for all left-right pairs, i.e., in quadratic time. The key observation is based on the following sparsity property of the point set. We already know that the closest pair of points is no further apart than dist= min(d_Lmin, d_Rmin). Therefore for each point p of the left of the dividing line we have to compare the distances to the points that lie in the rectangle of dimensions (dist, 2 ⋅ dist) to the right of the dividing line, as shown in the figure. And what is more, this rectangle can contain at most six points with pairwise distances at most d_Rmin. Therefore it is sufficient to compute at most 6n left-right distances in step 4. The recurrence relation for the number of steps can be written as T(n) = 2 T(n/2) + O(n), which we can solve using the master theorem to get O(n log n).

As the closest pair of points define an edge in the Delaunay triangulation, and correspond to two adjacent cells in the Voronoi diagram, the closest pair of points can be determined in linear time when we are given one of these two structures. Computing either the Delaunay triangulation or the Voronoi diagram takes O(n log n) time. These approaches are not efficient for dimension d>2, while the divide-and-conquer algorithm can be generalized to take O(n log n) time for any constant value of d.