An Efficient Comparison-Based Deterministic Algorithm to Solve the Closest Pair Problem

A simple and efficient algorithm is proposed to solve the closest pair problem of points in k-dimensional space. The algorithm presorts the points according to their values of one dimension and then only computes the distances of point pairs which may be closer than the current closest pair. Empirical analysis shows that in the average case the number of distance computations performed is of O(1) and the number of comparisons performed, if not including those in the presorting, is of O(n).