7

I am struggling to wrap my head around how the divide and conquer algorithm works for dimensions greater than 2, specifically how to find the closest pair of points between two sub-problems.

I know that I need to only consider points within a distance d of the division between the two on the x axis.

I know that in the 3d case I need to compare each point to only 15 others.

What I don't understand is how to choose those 15 points. In the 2d case, one simply sorts the values by y value and goes through them in order. In the 3d case, however, each point needs to be compared to the 15 points closest to it on both the y and z axes. I can't seem to find a way to determine what those 15 points are in a way that doesn't have a worst case of O(n^2)...

What am I missing here?

DonGato
  • 93
  • 1
  • 4

1 Answers1

0

A simple solution is to create an octree or a k-d tree, with all the points and then use it to find the nearest point for every point. That is O(N*log N) for the average case.

A faster solution that I think is O(N) for the average case can be implemented considering the following idea:

If you partition the space in half (say by some axis aligned plane), you get the points divided in two subsets, A and B, and the two nearest points can be both in A, both in B or one in A and one in B.

So, you have to create a queue of pairs of 3d boxes, ordered by the minimum distance between them and then:

1) Pick the first pair of boxes from the queue

2) If both boxes are the same box A, divide it in half in two boxes B and C and push the pairs (B, B), (C, C) and (B, C) into the queue.

3) If they are different (A, B), divide the biggest (for instance, B) in half obtaining boxes C and D and push into the queue the pairs (A, C) and (A, D).

4) Repeat.

Also, when the number of points inside the pair of boxes goes below some threshold you may use brute force to find the nearest pair of points.

The search stops once the distance between the two boxes in the pair at the top is bigger than the minimal distance found so far.

salva
  • 9,943
  • 4
  • 29
  • 57
  • 1
    What is the name of the o(n) algorithm that you have described? Is there any reference link for the algorithm? – Mahmudur Rahman Jun 26 '18 at 11:38
  • 3
    The name of that algorithm is "it doesn't exist". One can show that the best comparison-based algorithm for the closest pair problem cannot be faster than O(n*log(n)) in the worst case. – facetus Jun 11 '20 at 07:04