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
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:
- Split the list L at its middle, obtaining Lleft and Lright.
- Recursively solve ClosestPair(Lleft) and ClosestPair(Lright). Let the corresponding shortest distances obtained by δleft and δright.
- 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 Lleft and a point in Lright.
- 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).