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?

Beggary

Define the "closest pair algorithm" for us. – Individuality

given several points on a 2-D object find the two points that are the closest – Beggary

Answer 1

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

Manicotti

thanks how would that changes with 6 pair, (1,2)(1,11)(7,8)(9,9)(13,3)(13,4) – Beggary

@Beggary Actually I dont really understand your question. The algorithm does not change at all with the input size. I gave you a description how your example input would be processed. You can work out further examples on your own. – Manicotti

Sorry, I am trying to solve a larger problem and understand half of it – Beggary

I get the divide part, and what I am having trouble with is when comparing to subsets. Do you compare the shortest distance between in each of those subsets? For example in subset one the shortest distance in 5 and in subset two the shortest distance is 3. We just compare 5 and 3 and have no need to compare the actual point in the sub set – Beggary

If you do the sorting at the beginning (before the recursive function call) then you wouldn't need to do that in each recursive call. You would, however, need a way to separate the elements from the sorted array of all points in linear time O(n), which can be done by using hashes/sets. – Chevrotain

Answer 2

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

Sterling

Thanks, here is where I am getting confused. Lets say you have 12 pairs and you break it into 4 subsets of 3. One the left side you have pairs 1-6. You found the shortest of 1-3 and 4-6. To find the middle value do you need to compare the shortest distance of 1 to 4,5,6, then 2 to 4,5,6 then 3 to 4,5,6. Once that is done does that give you middle value. Is that correct – Beggary

No, you don't have 12 pairs and you don't break the pairs into subset. You have a number of POINTS and you break the POINTS into TWO subsets. – Sterling

So the points are broken into two subsets and those subsets are broken in two smaller subsets. Then find the shortest distance between each of the points in the subsets, correct? So we now have L(Left) and L(right) but we still need to find L(left-right). This is where I am getting confused. Do we compare all the points in L(left) to all points in L(right) to get L(left-right)? – Beggary

No, you break the points into two subsets. Then you run the shortest-pair algorithm recursively on those. Once the recursive invocations return, you check if there is a shorter distance available than any of the two returned by the recursive calls. Because you have already an upper bound for the distance (the min result returned by the recursive call), you don't need to consider all points from left and right regions, but only those sufficiently near to the split line. – Sterling

Answer 3

I think I know what algorithm you're talking about. I could recount it here myself, but the description given in Introduction to Algorithms is by far superior to what I can produce. And that chapter is also available on google books: enjoy. (Everybody else can find problem description there too)

Tuberose

Answer 4

Maybe Linear-time Randomized Closest Pair algorithm will help. There you can find the pair in expected time O(n).

Duane