Engineering the Divide-and-Conquer Closest Pair Algorithm

We improve the famous divide-and-conquer algorithm by Bentley and Shamos for the planar closest-pair problem.For n points on the plane,our algorithm keeps the optimal O(n log n)time complexity and,using a circle-packing property,computes at most 7n/2 Euclidean distances,which improves Ge et al.’s bound of(3n log n)/2 Euclidean distances. We present experimental results of our comparative studies on four different versions of the divide-and-conquer closest pair algorithm and propose two effective heuristics.