Engineering the Divide-and-Conquer Closest Pair Algorithm

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