Ближайшая пара очков в 3+ измерениях (разделите и покорите)

Question

Я изо всех сил пытаюсь обернуть голову тем, как работает алгоритм разделения и покоя для измерений более 2, в частности, как найти ближайшую пару точек между двумя суб- проблемы.

Я знаю, что мне нужно рассматривать только точки на расстоянии d деления между двумя на оси x.

Я знаю, что в 3d-случае мне нужно сравнить каждую точку только с 15 другими.

Я не понимаю, как выбрать эти 15 баллов. В случае 2d один просто сортирует значения по значению y и проходит через них по порядку. Однако в трехмерном случае каждая точка должна сравниваться с ближайшими к ней 15 точками как на осях y, так иz. Кажется, я не могу найти способ определить, что такое 15 баллов, что не имеет худшего случая O(n^2) ...

Что мне здесь не хватает?

Answer 1

Простым решением является создание октета или дерева k-d со всеми точками, а затем их использование для нахождения ближайшей точки для каждой точки. Это O (N * log N) для среднего случая.

Более быстрое решение, которое я думаю, O (N) для среднего случая может быть реализован с учетом следующей идеи:

Если вы разделите пространство пополам (скажем, по некоторой оси выровненной плоскости), вы получите точки, разделенные на два подмножества, A и B, а две ближайшие точки могут быть как в A, так и в B, или в одном в A и в одном из B.

Итак, вам нужно создать очередь пар 3d-боксов , упорядоченные по минимальному расстоянию между ними, а затем:

1) Выберите первую пару коробок из очереди

2) Если оба блока являются одним и тем же полем A, разделите его пополам в двух блоках B и C и вставьте пары (B, B), (C, C) и (B, C) в очередь.

3) Если они отличаются (A, B), разделите наибольший (например, B) половину, получая ящики C и D и вставляя в очередь пары (A, C) и (A, D) ,

4) Повторите.

Кроме того, когда количество точек внутри пары коробок опускается ниже некоторого порога, вы можете использовать грубую силу для поиска ближайшей пары точек.

Поиск останавливается, как только расстояние между двумя ящиками в паре вверху больше минимального расстояния, найденного до сих пор.