Description

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.