CODEWITHSUNDEEP
algorithm
Amumu
Amumu

Reputation: 18572

Why do we compare at most 7 points in closest pair algorithm?

So, if within δ * 2δ rectangle R, we only need to compare one point from the left side to 7 points on the right side. What I don't understand is, despite reading the proof, inside R we can fill as many points as we want inside the rectangle which may exceed the total number of 7. Imagine if we have δ = 2, a point p(1.2, 1.1) on the left side, and on the right side, we have a whole bunch of q, such as q(1.5, 1.7) , q(1.4, 1.3),.....how can only comparing 7 points detects the closest pair? I thought that we must compare every points within rectangle R if it is the case. Please help me.

Upvotes: 7

Views: 5570

Answers (1)

Mig
Mig

Reputation: 796

There may only be 6 points inside your rectangle, since that's the maximum number of points that you can put in a rectangle with sides δ and 2δ maintaining the property that they are at least δ distant from each other.

The way to lay those 6 points is shown in the figure below:

How to lay 6 points \delta apart from each other in a δ × 2δ rectangle

You can check for yourself that there's way of putting another point inside the rectangle without violating the distance property. If you add more than 6 points, they would be less than δ apart, which is a contradiction, since δ is supposed to be the distance between the closest pair.

Since there may be a maximum of 6 points, testing 7 will guarantee that you find the solution.

I got figure 1 from these UCSB slides, which may be useful to you.

Upvotes: 14

Related Questions