Time-Optimal Heuristic Algorithms for Finding Closest-Pair of Points in 2D and 3D

摘要

Given a set of n points in 2D or 3D, the closest-pair problem is to find the pair of points whichare closest to each other. In this paper, we give a new O(n log n) time algorithm for both 2Dand 3D domains. In order to prove correctness of our heuristic empirically, we also providejava implementations of the algorithms. We verified the correctness of this heuristic by verifyingthe answer it produced with the answer provided by the brute force algorithm, through 600 trialruns, with different number of points. We also give empirical results of time taken by runningour implementation with different number of points in both 2D and 3D.