An Improved Algorithm for Finding the Closest Pair of Points

摘要

As early as in 1975, Shamos and Hoey first gave an O(n lg n)-time divide-and-conquer algorithm (SH algorithm in short) for the problem of finding the closest pair of points. In one process of combination, the Euclidean distances between 3n pairs of points need to be computed, so the overall complexity of computing distance is then 3n lg n. Since the computation of distance is more costly compared with other basic operation, how to improve SH algorithm from the aspect of complexity of computing distance is considered. In 1998, Zhou, Xiong and Zhu improved SH algorithm by reducing this complexity to 2n lg n. In this paper, we make further improvement. The overall complexity of computing distances is reduced to (3n lg n)/2, which is only half that of SH algorithm.