Finding the Closest Pair of Points: A Randomized Approach
We have discussed the divide-and-conquer technique to develop an O(nlogn) time algorithm for the problem of finding the closest pair of points in the plane. Here we will study and implement a different algorithm(randomized) for this problem,
The basic idea of the algorithm is very simple. We’ll consider the points in random order, and maintain a current value δ for the closest pair as we process
the points in this order. When we get to a new point p, we look “in the vicinity “of p to see if any of the previously considered points are at a distance less than δ from p. If not, then the closest pair hasn’t changed, and we move on to the next point in the random order. If there is a point within a distance less than δ from p, then the closest pair has changed, and we will need to update it.
The details are given in the file attached.