Recursively compute closest pairs

2
votes

I am trying to perform the closest pairs algorithm - there is one area however where I am totally stuck.

The problem can be solved in O(n log n) time using the recursive divide and conquer approach, e.g., as follows:

1) Sort points according to their x-coordinates.

2) Split the set of points into two equal-sized subsets by a vertical line x=xmid.

3) Solve the problem recursively in the left and right subsets. This yields the left-side and right-side minimum distances dLmin and dRmin, respectively.

4) Find the minimal distance dLRmin among the set of pairs of points in which one point lies on the left of the dividing vertical and the second point lies to the right.

5) The final answer is the minimum among dLmin, dRmin, and dLRmin.

My problem is with Step 3: Let's say that you've split your 8 element array into two halves, and on the left half you have 4 points - 1,2,3 and 4. Let's also say that points 2 and 3 are the closest pair among those 4 points. Well, if you keep recursively dividing this subset into halves, you will eventually end up calculating the min between 1-2 (on the left), you will calculate the min between 3-4 (on the right), and you will return the minimum-distance pair from those two pairs..

HOWEVER - you've totally missed the distance between 2-3, as you've never calculated it since they were on opposite sides... so how is this issue solved? Notice how Step 4 comes AFTER this recursive process, it seems to be an independent step and only applies to the end result after Step 3, and not to every subsequent division of the subarrays that occurs within Step 3.. is it? Or is there another way of doing this that I'm missing?

1
algorithmrecursionclosest-points
You perform steps 4 and 5 also in each recursive call so you don't miss out on any possibility. – Abhishek Bansal
Excellent, that's what I thought but couldn't figure out.. Thanks that makes total sense.. – matt

1 Answers

3
votes

The steps are a bit misleading, in that steps 2-5 are all part of the recursion. At every level of recursion, you need to calculate dLmin, dRmin, and dLRmin. The minimum of these is returned as the answer for that level of recursion.

To use your example, you would calculated dLmin as the distance between points 1 and 2, dRmin as the distance between points 3 and 4, and then dLRmin as the distance between points 2 and 3. Since dLRmin is the smallest in your hypothetical case, it would be returned.