[Math] “Closest pair of points” algorithm

Question

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

Closest pair of points – algorithm.

Can someone explain it in greater detail?

Answer 1

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.