Closest Pair of Points in 3+ Dimensions (Divide and Conquer)

Question

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?

Mull

Answer 1

For a small number of points in 3D closest points algorithm , do a brute force search. Otherwise, divide the points into a front half and back half, and recursively solve to find the closest distance in each half. Now we just need to check points that cross from one half to the other across the mid-plane. However, we only need to worry about a region close the this mid-plane, and so we end up being concerned with points near a 2-D plane. So we use an approach similar to our algorithm for Closest Points in 2-D (a plane) to deal with this strip: we divide the points close to the plane into a left and right half, and recursively solve in each half. Then we just need to concern ourselves with points that are close to the dividing midplane, so we end up with a long narrow cuboid region of concern that is kind of like a 1-D line, so we use an approach similar to the 1-D case of points on a line (sort the points and check from each point to the few next point(s)). For the number of points to check from the midpoint in a 3d point algorithm is 31. (It is likely ok to check fewer points, but 31 is the easiest to justify.) Yδ contains points in a tall cuboid whose cross-section is a square of 2δ × 2δ, bisected by xmid and zmid. Now if we imagine breaking up this cuboid into small cubes with edge-length δ/2, if there were two points in a cube, their distance would be less than δ. Notice each cube is entirely in the left/front quadrant, the left/back quadrant, the right/front quadrant, or the right/back quadrant. We know that 2 points both on the left, or both on the right, or both in the back, or both in the front have distance greater than or equal to δ. This gives us a contradiction, so each cube must have at most one point in it.

Credits to : Shelby Kimmel (Professor of Computer Science at Middlebury College)

Gamecock

Answer 2

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.

Harijan

What is the name of the o(n) algorithm that you have described? Is there any reference link for the algorithm? – Chatman

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. – Waylay