Divide and Concur

Prob Closest Pairs of Points Given a set of points in the two- dimensional plane, find a pair of points in , such that the Euclidean distance is smallest.

Algorithm Divide and Concur Algorithm The idea is to continue dividing the problem into two sub-problems of “almost” the same size until the problems are of size 3 and smaller.

1. We start by sorting the points in by -coordinate and -coordinate and store these orderings in arrays and .
2. We find a vertical line which divides the points into two subset of almost equal size. Note that this can be done using the ordered array based on the -coordinate.
3. Suppose is the distance of the closest pair in the left point set and is for the right point set, then . Then, we want to check if there is a point on the left and a point on the right with a smaller distance than .
4. Suppose we are processing the point with the black arrow (moving from bottom to top). We only need to consider points whose -coordinate is less than its -coordinate plus .

Prop The time complexity of the above example is in .