closest pair algorithm

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).

If you mean this algorithm you do the following:

1. Sort points: (1,2) (1,11) (7,8)
2. Build two subsets: (1,2) (1,11) and (7,8)
3. Run the algorithm on (1,2) (1,11) and on (7,8) separately <= this is where the recursion comes. The result is dLmin = 9 and dRmin = infinity (there is no second point on the right)
4. dLRmin = sqrt(45)
5. result = min(dLmin, dRmin, dLRmin) = sqrt(45)

The recursion consists of the same steps as above. E.g. the call with (1,2) and (1,11) does:

1. Sort points: (1,2) (1,11)
2. Build two subsets: (1,2) and (1,11)
3. Run the algorithm on (1,2) and on (1,11) separately <= again recursion calls. The result is dLmin = infinity and dRmin = infinity
4. dLRmin = 9
5. result = min(dLmin, dRmin, dLRmin) = 9