Closest pair of points

问题:

In http://en.wikipedia.org/wiki/Closest_pair_of_points_problem we can see that it mentions that is at most 6 points that is closest to the point on the other half, which can be represented as the graph below:

My question is for point P1 and Point P2, the distance to the red point will exceed sqrt(2)*d, why it is part of the solution? Why it is not at most 4 points that is closest to P rather than at most 6 points? Thanks.

回答1:

P1 and P2 are not part of the solution, but they have to be examined on the way to the solution, because the algorithm examines all points in the box, and P1 and P2 are in the box.

Note that no such point as your Q can exist, because by hypothesis the minimum distance between points in the right-hand half of the diagram is d.

Edited to add: you seem to think that the Wikipedia article is making a claim like this:

• There may be up to 6 points on the right side of the line that are within a distance d of P.

This claim would be false. But the article does not make such a claim. Instead, it makes two separate claims, both of which are true:

1. All the points on the right side of the line that are within a distance d of P are inside the box.
2. There may be up to 6 points in the box.

回答2:

The bound is only important for complexity estimation. Code-wise, you may simply scan up and down within the distance dRmin. The bound here suggest that you'll at most see 6 points in each such scan, making this O(1).

回答3:

We are only counting the maximum number of points that can lie in the right d x 2d rectangle. Since any two points are constrained to have a minimum distance of d, we can place at most 6 points in the rectangle while satisfying this constraint, as shown in the figure.

Note that the points on the right side that are within d distance from P should all lie within a circular segment of a circle centered at P and whose radius is d. There can be at most 4 points in this segment. However, finding the number of points within a segment is more complicated than finding the number of points within a rectangle. So we use the rectangle instead and incur an extra cost of having to search for at most 2 additional points.