Divide and conquer for the closest-pair problem revisited

Abstract

In this paper the divide-and-conquer approach to the two-dimensional closest-pair problem is studied. A new algorithm is proposed by which a closest pair, i.e. a pair of points whose distance δ is smallest among a set of N points, is found in θ(N) expected time when the points are drawn independently from the uniform distribution in a unit square. The worst-case running time of the algorithm is θ(N log² N). The method is to project the points onto one of the coordinate axes, and to compute an initial guess for the smallest distance δ by considering the [N/2] pairs of successive projected points. The shortest of these pairwise distances is a good approximation for the final δ. It is then used in the subsequent merge phases of the divide-and-conquer algorithm to keep the average work minimal. A modification of the basic algorithm guarantees θ(N) performance in the average case and θ(N log N) performance in the worst case.

Keywords:

• Closest pair
• divide and conquer
• computational geometry

C.R. Categories:

• F.2.2