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

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

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

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

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

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


algorithm closest-points divide-and-conquer
person DonGato    schedule 25.02.2016    source источник

Ответы (1)


arrow_upward
0
arrow_downward

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

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

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

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

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

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

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

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

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

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

person salva    schedule 22.11.2017
comment
Как называется описанный вами алгоритм o(n)? Есть ссылка на алгоритм? - person Md. Mahmudur Rahman; 26.06.2018
comment
Название этого алгоритма - его не существует. Можно показать, что лучший алгоритм, основанный на сравнении, для задачи о ближайших парах не может быть быстрее, чем O(n*log(n)) в худшем случае. - person facetus; 11.06.2020