closest pair algorithm

Question

I am trying to understand the closest pair algorithm. I understand about dividing the set in half. But I am having trouble understanding how to recursively compute the closest pair. I understand recursion, but do not understand how to compute the closest pair by recursion. If you have (1,2)(1,11)(7,8) how would recursion work on these?

Answer 1

the basic idea of the algorithm is this.

You have a set of points P and you want to find the two points in P that have the shortest distance between them.

A simple brute-force approach would go through every pair in P, calculate the distance, and then take the one pair that has the shortest distance. This is an O(n²) algorithm.

However it is possible to better by the algorithm you are talking about. The idea is first to order all the points according to one of the coordinates, e.g. the x-coordinate. Now your set P is actually a sorted list of points, sorted by their x-coordinates. The algorithm takes now as its input not a set of points, but a sorted list of points. Let's call the algorithm ClosestPair(L), where L is the list of points given as the argument.

ClosestPair(L) is now implemented recursively as follows:

1. Split the list L at its middle, obtaining L_left and L_right.
2. Recursively solve ClosestPair(L_left) and ClosestPair(L_right). Let the corresponding shortest distances obtained by δ_left and δ_right.
3. Now we know that the shortest distance in the original set (represented by L) is either one of the two δs, or then it is a distance between a point in L_left and a point in L_right.
4. Se we need still to check if there is a shorter distance between two points from the left and right subdivision. The trick is that because we know the distance must be smaller than δ_left and δ_right, it is enough to consider from both subdivisions points that are not farther than min(δ_left, δ_right) from the dividing line (the x-coordinate you used to split the original list L). This optimization makes the procedure faster than the brute-force approach, in practice O(n log n).