как найти дальних соседей в евклидовом пространстве?

Question

При заданном наборе P из n точек в 2D для любой точки x в P, какой самый быстрый способ определить дальнего соседа x? Самым дальним соседом мы обозначаем точку в P, которая имеет максимальное евклидово расстояние до x.

Answer 1

Насколько мне известно, текущий стандартный алгоритм поиска kNN для различных деревьев (R-Trees, quadtree, kd-trees) был разработан:

GR Hjaltason и H. Samet. , «Дистанционный просмотр в пространственных базах данных», ACM TODS 24 (2): 265--318. 1999

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

В алгоритме basi c используется очередь с приоритетами. Очередь может содержать узлы дерева, а также записи данных, отсортированные по расстоянию до точки поиска. На начальном этапе он добавляет узел root в очередь с приоритетами. Затем повторяйте следующее до тех пор, пока не будет найдено k записей:

1. Возьмите первый элемент из очереди. Если это запись, верните ее. Если это узел, добавьте все элементы узла в очередь с приоритетами.
2. Повторите 1.

В документе описывается реализация R-деревьев, но они утверждают, что ее можно применять к большинству древовидных структур. Я сам реализовал ближайшую версию соседа для R-Trees и PH-Trees (специальный тип дерева квадрантов), оба в Java. Я думаю, что знаю, как сделать это эффективно для KD-Trees, но я считаю, что это несколько сложно.