Pancake's blog

By Pancake, 11 years ago, In English

I have recently learnt the O(NlogN) solution which solves the closest pair problem based on a divide-and-conquer approach. However , I still have a question about it . I assume all N points are unique.

In the case where the closest pair in the current sub-problem consists of one point to the left of the middle line , and another to the right of the middle line , we have to :

  • list the points that satisfy abs(x - xmid) < D : D is the shortest distance so far.
  • sort these points with respect to their y-coordinates (in non-decreasing order)
  • Loop on those points in order , for each point there is a constant number of points that exist within the 2D * D rectangle and any point outside of this rectangle can't improve the answer.

I know that within a 2D * D rectangles there can exist at most 6 points such that any pair of them is at least D units of distance apart. Hence , in the previous method , I think we should examine at most 5 neighbor points within that rectangle. However , many websites claim that the upper bound is 7 or 8. I can't get why. May someone explain the reason ? Also , I'm interested in a formal proof for the 6-points-claim. I only found intuitive ones but they aren't very convincing. Thanks.

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

say your proof for "I think we should examine at most 5 neighbor points within that rectangle". but I think it's not important that you check 5 points or 6 points, its important that the number of points in the rectangle have the constant upper_bound for all possible situation.

  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh sure , the exact number of points doesn't affect the asymptotic complexity but I have a theoretical curiosity :) I think it's a bit hard to write down a formal proof for that.