In http://en.wikipedia.org/wiki/Closest_pair_of_points_problem we can see that it mentions that there are no more than 6 points closest to the point on the other half, which can be represented as a graph below:
My question is that point P1 and point P2, the distance to the red point will exceed sqrt (2) * d, why is it part of the solution? Why is it not at most 4 points that are closest to P than not more than 6 points? Thank.
P1 and P2 are not part of the solution, but they need to be studied on the way to the solution, since the algorithm checks all the points in the field, and P1 and P2 are in the field.
, , Q, d.
: , , :
. . , :
, d x 2d. d, 6 , , .
, , d P, P d. 4 . , . , 2 .
. , dRmin. , 6 , O (1).
