Closest pair of points Planar case

Question

I am looking at the wikipedia entry for how to solve this. It lists five steps

1.Sort points along the x-coordinate

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 will give the left-side and right-side minimal distances dLmin and dRmin respectively.

4.Find the minimal distance dLRmin among the pair 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.

The fourth step I am having trouble understanding. How do I choose what point to the left of the line to compare to a point right of the line. I know I am not supposed to compare all points, but I am unclear about how to choose points to compare. Please do not send me a link, I have searched, gone to numerous links, and have not found an explanation that helps me understand step 4.

Thanks

Aaron

Answer 1

The answer to your question was in the next paragraph of the wikipedia article:

It turns out that step 4 may be accomplished in linear time. Again, a naive approach would require the calculation of distances for all left-right pairs, i.e., in quadratic time. The key observation is based on the following sparsity property of the point set. We already know that the closest pair of points is no further apart than dist = min(dLmin,dRmin). Therefore for each point p of the left of the dividing line we have to compare the distances to the points that lie in the rectangle of dimensions (dist, 2 * dist) to the right of the dividing line, as shown in the figure. And what is more, this rectangle can contain at most 6 points with pairwise distances at least dRmin. Therefore it is sufficient to compute at most 6n left-right distances in step 4. The recurrence relation for the number of steps can be written as T(n) = 2T(n / 2) + O(n), which we can solve using the master theorem to get O(n log n).

I don't think I can put it much clearer than they already have, but do you have any specific questions about this step of the algorithm?