Can I compute closest split pair of points where distance is strictly less than delta I've been studying the closest pair algorithm lately and I found this to be an extremely good and intuitive resource: http://serverbob.3x.ro/IA/DDU0221.html. It is also explained in section 33.4, "Finding the closest pair of points" of introduction to algorithms, third edition  by CLRS.

I understand why I'd need 7 comparisons for a non pairwise distinct set of points and only 5 otherwise (33.4-2). Both of them follow from the fact that I can fit only 4 points, at least Delta away from each other, on a Delta x Delta box.

What I've been wondering though, is if I could trim the number of comparisons down to 3 if I included only points strictly less than Delta away from the middle line, in the middle Delta x 2 Delta strip. The reasoning is that I already have a pair of points Delta away from each other from the recursive calls, I only need points less than Delta and I can only fit 2 points Delta away from each other AND less than Delta from the middle line on each side.

Have I missed something or can I really just compare the 3 following points of every point in a middle strip only containing points strictly less than Delta from the center?

Edit:
I have started a bounty for a very similar question on stack overflow also and we have come up with a very interesting discussion there. So I'm linking it here. We've also started a very insightful chat here.
Yes, as you have observed, we can just compute pair of points whose distances are strictly less than $\delta$ in the "combine" step of the "divide-conquer-combine" algorithm, where we examine the minimal distance between the points to the left and the points to the right. 

However, it is not enough to just compute the next 3 points.





The above graph, taken from CLRS, illustrates the original argument for 7 in the case of non-pairwise distinct points and for 5 in the case of pairwise distinct points. For the sake of clearer explanation, assume the central line $l$ is the vertical axis and $\delta=\delta_L=\delta_R=1000$. Let the strip consist of the area between the line $x=1000$ and $x=1000$, excluding those two lines. This strip contains only the points that are strictly less than 1000 away from the central line $l$. Suppose all distinct points in the strip in the ascending order of vertical coordinate are $s_0, s_1, s_2, s_3, s_4$.

Suppose we have verified that $d(s_0,s_i)\ge1000$ for $i=1,2,3$. Can we conclude that there is no point $s$ such that $d(s_0,s)&lt;1000$?

No. It might happen that
$$\begin{align}\\
s_0&amp;=(79,0)\\
s_1&amp;=(-921,1)\\ 
s_2&amp;=(999,500)\\  
s_3&amp;=(-999, 998)\\  
s_4&amp;=(79, 999)
\end{align}$$

Note that $d(s_0, s_4)= 999&lt;1000$. In fact, $d(s_i,s_j)\gt1000$ for all $i$ and $j$ except $d(s_0, s_4)$.
$$\begin{align}
d(s_0, s_1)&amp;=\sqrt{1000001}  \\
d(s_0, s_2)&amp;=\sqrt{1096400}  \\
d(s_0, s_3)&amp;=\sqrt{2158088}  \\
d(s_0, s_4)&amp;=\sqrt{998001}  \\
d(s_1, s_2)&amp;=\sqrt{3935401}  \\
d(s_1, s_3)&amp;=\sqrt{1000093}  \\
d(s_1, s_4)&amp;=\sqrt{1996004}  \\
d(s_2, s_3)&amp;=\sqrt{4240008}  \\
d(s_2, s_4)&amp;=\sqrt{1095401}  \\
d(s_3, s_4)&amp;=\sqrt{1162085}  \\
\end{align}$$
So if we only compute the distance with the next 3 points, we will not find that shortest edge from $s_0$ to $s_4$ at the end of the algorithm.

The above counterexample shows that it is not sufficient to just compare 3 following points of every point in a middle strip only containing points strictly less than $\delta$ from the center line, even if we assume that all points are distinct.