I'm having a problem with understanding the difference between two solution of of closet pair of point in plane.
According to the the Wikipedia when we are merging two planes we need to check at most 6 points. Why 6 points? because they draw a rectangle in the other plane and claim that at most 6 points can be in the other side. And the following picture is the summery of the their solution:
I got satisfy with this solution, but I have problem with the another solution which has been mentioned in this thread. According to this solution we should check at most 7 points. How 7 points? Due to figure there are two separate square with one edge overlapping. My first question is how they have draw these two squares or one triangle. I mean how they located this triangle, they've just mentioned that its center is on line L, but they haven't mentioned about how they draw it with respect to two other points, why they haven't slip it upper or downer?
And in sum up are these two solutions different from each other or not ?
Best Answer
AFAIR the algorithm works with the divide-and-conquer paradigm. It splits the plane (and the set of points!) by 'half', solves the problem recursively and then merges the results. The merging is done in such way, that the points get ordered along the splitting line. Then you just scan the left part and the right part in parallel to find a pair crossing the border, which might be closer than the closest pair of points found so far in either part (whose distance is $\delta$ here).
Of course you can skip points that are farther than $\delta$ from the border, as well as point that are lower than $\delta$ below the current point — those certainly will NOT make a pair closer than $\delta$. That way you have a grey area which may contain a point sought. However you already know that there is no pair of point on either side, which are closer than $\delta$. Based on that you can prove, that there can be at most 6 such points in the grey area, hence you don't need to keep more than 6 most recently checked points for future comparisions in a single merge pass.
EDIT
Look again at the description in the right part of this image, which shows 6 dots but tells about 8 points:
Apparently authors assumed that input data may contain duplicated points, which fall into separate subsets during the recursive 'divide' phase at some point. Such duplications are usually forbidden in geometric algorithms — most often when someone defines a quadrilateral ABCD, you don't expect it to be actually a triangle due to D=A, do you? Also, if duplicates are allowed, then there might be any number of the single point duplicates; I can't understand, why they assume there will be only two.
Anyway if they presume that every point may appear max. twice, hence there might be maximum 8 points in the indicated area, one of which is the point currently analyzed, then that current point needs to be checked with at most 7 other points.
OTOH authors of the algorithm described in Wikipedia assumed no duplicates and similary find out there can be at most 6 points in the $\delta\,\times\,2\delta$ rectangle. Then the next point analyzed on one side of the splitting line needs to be checked against at most 6 points from the other side.