Nearest pair of glasses in 3+ dimensions (divide and conquer)

Question

I'm struggling to wrap my head around how the separation and rest algorithm works for measurements of more than 2, in particular, how to find the nearest pair of points between two sub-problems.

I know that I need to consider only points at a distance d from the division between them on the x axis.

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

I do not understand how to choose these 15 points. In the case of 2d, the y values ​​are simply sorted and passed in order. However, in the 3d case, each point must be compared with the nearest 15 points on the y and z axes. It seems I can’t find a way to determine what 15 points are, which does not have the worst case O(n^2) ...

What am I missing here?

Answer 1

A simple solution is to create an octet or kd tree with all the points, and then use it to find the nearest point for each point. This is O (N * log N) for the middle case.

A faster solution, which, in my opinion, is O (N) for the average case, can be implemented taking into account the following idea:

If you divide the space by half (say, on some plane aligned along the axis), you will get points divided into two subsets: A and B, and the two closest points can be either in A or in B or in one of A and one in B.

So, you need to create a queue of pairs of three-dimensional boxes ordered by the minimum distance between them, and then:

1) Select the first pair of cells from the queue

2) If both fields are the same field A, divide it in half into two fields B and C and insert the pairs (B, B), (C, C) and (B, C) in the queue.

3) If they are different (A, B), divide the largest (for example, B) half, receiving boxes C and D and inserting pairs (A, C) and (A, D) into the queue.

4) Repeat.

In addition, when the number of points within a pair of cells goes below a certain threshold, you can use brute force to search for the nearest pair of points.

The search stops as soon as the distance between the two cells in the pair above is greater than the minimum distance found so far.