Mashilamani Sambasivam, Texas A&M University, USA

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

Closest-pair, Algorithm, Heuristic, Time-Optimal, Computational Geometry, 2D, 3D