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?

Kisung

Nice question. Would you mind adding a brief introductory paragraph to give some context? – Burton

Added a few lines at the top, hope this fulfils the purpose. – Kisung

You cannot put an actual point in every square and not violate the condition. Try placing the actual points. – Stallard

@Stallard Looks like I have started to visualize what you mean. With the circle present, points in adjacent squares will violate the condition of being not closer than delta. I see that physically, in a drawing software. Is there a mathematical way? – Kisung

@MMA See my answer below. – Stallard

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.

Philippa

This is correct if you run the algorithm symmetrically (i.e. the left part and the right part play the same role). However this is not the variant usually discussed. Normally you pick a side (left or right), go over points on that side from bottom to top, and then examine points on the other side that might be close to the current point. These points may be either above or below the current point. – Splinter

Answer 2

You can put 9 points on the grid actually. If (0,0) is center and assuming delta=1, you can have 9 points at (-1,-1), (-1,0),..., (1,1).

Proof that it is only at most 9:

Even at optimal packing, you can only have 3 layers of circles each with radius (1/2)with all the centers inside a 2X2 square.

So, the difference drops down to 8 after this. To get to seven you have to assume that it is not a special case (I forgot the technical term for it, but it is a popular assumption in computational geometry. It also states that 3 points cannot be on a same line. It is called "generality assumption" or something like that.

Stallard

Would you mind elaborating the last part a little? Searching for "generality assumption" did not return anything. I really want to understand this. – Kisung

@MMA At this moment I cannot find any references. The assumption is, in general, no three points are on a line, and no 4 points on a plane, and not n+1 points on a n-hyperplane etc. – Stallard

@Stallard No, you don't need the generality assumption for this problem. I think your explanation is incorrect. We are only interested in one single point in the left (negative x) half-square. We know that all other points in that half-square are no closer than d to that point. We need to examine the other half. – Splinter

Answer 3

According to CLRS 33.4:

There're 2 points to the left of line l (see the most left 2 points), 2 points to the right of line l (see the most right 2 points), and 4 points on line l (both PL and PR are on the same points).

2 + 2 + 4 = 8

not including the self, so it's 8 - 1 = 7

e.g. we're counting the distance between PL (the upper point on l) and other points, let's do it counterclockwise:

• the 1st point (PL) is the most left one,
• 2nd (PL) is bottom left,
• 3rd (PL) is the bottom point on l,
• 4th (PR) is also the bottom point on l,
• 5th (PR) is the bottom right one,
• 6th (PR) is the upper right one,
• 7th (PR) is the upper point on l.

Patricia