Explanation of these seven points in finding the closest pair of points

Question

I am trying to grasp the explanation of the closest pair point problem in various literatures. While the basic approach is the same in all of them, divide-solve-combine (divide and conquer), and get linear time merge (combine/conquer), the actual implementation is subtly different among the articles and books.

The linear-time-merge is key here which tries to limit the number of points to be compared.

The way the points are being considered in the Kleinberg book is a bit different the way points are considered in this Wikipedia article or Cormen book.

Anyway, for the later two, we find nice explanations for the number of points to be considered here, and here, including many others.

For the problem in hand, please take a look at these slides (slide 32) for the Kleinberg book. The claim of 11 point gap is in the same slide. A more detailed explanation can be found here in page 6, section 6.2.5.6.

However, in the same page of the above mentioned slides (slide 32), we find a claim something like, "Still true if we replace 12 with 7."

I have failed to find an explanation of the above claim.

Please see the figure below,

If we consider the red point to be compared with those in the right half, the points in the right half should be in the shaded half circle. I have tried to put the extreme ones in blue. Still they are |5-(-2)|+1 = 8 and |5-15|+1 = 11 apart.

What is it I might be missing here?

Answer 1

Actually you do not need to compute the distance for the lower half of the points, since in your range if you consider points sorted according to y-axis then you start from bottom and go up considering only the points in the region above it.