# “Closest pair of points” algorithm

I'm having a problem understanding why I just have to consider the next 7 points in the

Can someone explain it in greater detail?

-

I've simply included the diagrams (here they're larger than on the webpage you linked us to!), along with the caption below the figure: "Key concepts".

Together, with thoroughly reading the "Correctness" (and proof of algorithm) section of the exercise, hopefully you'll be able to answer your question. If not, feel free to edit your post and specify, in much greater detail than you first provided us, what it is exactly that you're confused about. We'll be in a much better position that way to satisfactorily answer your question(s).

Figure #33.11: Key concepts in the proof that the closest-pair algorithm needs to check only $7$ points following each point in the array Y'.

(a) If $p_L \in P_L$ and $p_R \in P_R$ are less than $\delta$ units apart, they must reside within a $\delta \times 2\delta$ rectangle centered at line $1$.

(b) How $4$ points that are pairwise at least $\delta$ units apart can all reside within a $\delta \times \delta$. On the left are $4$ points in $P_L$, and on the right are $4$ points in $P_R$. There can be $8$ points in the $\delta \times 2\delta$ rectangle if the points shown on line $1$ are actually pairs of coincident points with one point in $P_L$ and one in $P_R$.

This last point may be the key, in terms of understanding why the there can be no more than $8$ points in a $\delta \times 2\delta$ rectangle. The maximal number of points in a $\delta \times \delta$ square, such that any pair of points is at least $\delta$ units of distance apart is at most $4$.

Why? Try dividing a $\delta \times \delta$ square into $4$ squares (each of dimension $\delta/2 \times \delta/2$. The maximum length between any possible two points in any given subdivided square is the length of its diameter: $\sqrt{2}\delta/2$, which is less than $\delta$. In this way, each such subdivided square can contain at most one point, and, thus, at most $4$ points can be contained in the $\delta \times \delta$ square.

-
Thank you. I now understand. ;) My problem was that I couldn't understand why the δ × 2δ rectangle has at most 8 points. But now I see that there will be a contradiction if there is more than 8 points. – user11775 Jun 16 '11 at 22:18
@user11775: Great! It isn't the easiest of webpages to read (tiny print), and the diagrams were pretty small (certainly hard to make out deltas and such!), but they seemed helpful to understanding the "key concepts" and "correctness" explanation. – amWhy Jun 16 '11 at 22:56

It's explained below the headline "Correctness". At most 8 points may reside in the $\delta \times 2\delta$ rectangle because at most 4 may be found in the left square and at most 4 may be found in the right square. With 8 points in total, it is enough to check for 7 points in the array $Y'$. The background of the proof is complicated and is described on the page you mentioned.

-
I know. I'm confused about the part: "it is easy to see that we need only check the 7 points following each point in the array Y′." – user11775 Jun 16 '11 at 19:58

There are 2 things to understand:

(1) The first is described well in the text you linked to: After finding the closest pair of points on the left side (denote the distance between them by $\delta_L$), and the closet pair of points on the right side (denote their distance by $\delta_R$), we are only interested in knowing whether there is an even closer pair of points, of which one lies in the left side and the other in the right side. So we're only interested in such pairs $(p_L, p_R)$ which are less than $\delta=min(\delta_L, \delta_R)$ units of distance apart. So the distance between $p_L$ and the the line $l$ (see figure $(a)$) must not be more than $\delta$ and the distance between $p_R$ and the line $l$ must not be more than $\delta$. That is, it's enough to only consider the points lying in the infinite vertical strip shown in figure $(a)$. Further, the vertical distance between $p_L$ and $p_R$ must not be more than $\delta$ (this is shown in figure $(b)$). So, we can first filter out all points lying outside the vertical strip (figure $(a)$). Then, remembering that we have the points sorted according to their $y$ coordinate, we see that it's enough to consider for each point, all the points above until we encounter a point more than $\delta$ units of distance apart vertically. How many points might we check until this happens? This is bounded from above by twice the maximal number of points in a $\delta \times \delta$ box, under the constraint that no two points are less than $\delta$ units of distance apart (remember that each of these two $\delta \times \delta$ boxes is entirely contained either in the left side or the right side, and recall how $\delta$ was defined). So, how many points is this?

This is the second part to understand, which is actually not really proved in the text you linked to: (2) The maximal number of points in an $\delta \times \delta$ box, such that any pair of points is at least $\delta$ units of distance apart is at most 4. The proof is easy: Divide the box to 4 boxes, each of size $\delta/2 \times \delta/2$. The diameter of each such box is $\sqrt{2}\delta/2$ which is less than $\delta$. Therefore, in each such small box you can have at most one point and hence there are at most 4 points in the $\delta \times \delta$ box.

-