A Simple Yet Fast Algorithm for the Closest-Pair Problem Using Sorted Projections on Multi-Dimensions

We present a simple greedy algorithm, QuickCP, for finding the closest-pair of points on a plane. It is based on the observation that if two points are close to each other, then it is very likely that their sorted projections to x-axis and/or to y-axis will reflect that closeness. Therefore we order our search starting from the pairs with closest x-projections (and closest y-projections) to find the closest pair quickly and make a fast exit. Empirical data up to 2(26) (over 60 million points) indicates that this approach quickly detects the closest pair and it is, on average 70% faster than the classical divide-and-conquer algorithm registering, to the best of our knowledge, the fastest recorded solution times in the literature for the planar closest-pair problem. A second contribution of our work is that QuickCP can be used as part of the divide-and-conquer algorithms to handle small sub-problems. Measurements on data up to 2(26) points show that this co-operation speeds up the basic divide-and-conquer algorithm on average 50%.