Closest pair of points

Question

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.

Grade

Answer 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.

Disappointed

Thanks, if "There may be up to 6 points on the right side of the line that are within a distance d of P." is false, what is the correct number of points? If it is less than 6 points, can we examine say only 5 points? – Grade

I think the maximum number of points in the right-hand half that are within a distance d of P is actually three. But the problem is, how do we arrange to examine those points and only those points? It is fairly easy to build a data structure so that we can efficiently list the points within the box, but what data structure will do the job for the circular segment? – Disappointed

Yea, thanks for the help, I am not sure whether I could ask a question that is not very related to the question: may I know what software you are using to draw the diagram? That seems pretty nice :) – Grade

Hi Gareth, if I wish draw similar graph in windows 7, do you have any recommended graphic drawing software (like OmniGraffle for Mac)? – Grade

What if we trim down the points in the box to strictly less than d? That way we will only have 3 points in the box that are d away from each other – Deforce

Answer 2

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.

Demineralize

No, you cannot have 6 points that are within d distance from P. I have edited the post to make this more clear. Hope this helps. – Demineralize

Answer 3

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).

Melville