Нахождение самой дальней точки в одном наборе из другого набора

Question

Моя цель - более эффективная реализация алгоритма, поставленного в этом вопросе .

Рассмотрим два набора точек (в N-пространстве. 3-пространство для примера случая цветового пространства RGB, тогда как решение для 1-пространства 2-пространства отличается только в расчете расстояния). Как найти точку в первом наборе, которая является самой далекой от ближайшего соседа во втором наборе?

В примере с 1 пробелом, учитывая множества A: {2,4,6,8} и B: {1,3,5}, ответ будет 8, так как 8 находится в 3 единицах от 5 (его ближайший сосед в B), в то время как все остальные члены A находятся всего в 1 единице от их ближайшего соседа в B. таким образом, что это не в более высоких измерениях.

Решение исходного вопроса включает в себя сравнение грубой силы каждой точки в одном наборе (все R, G, B, где 512> = R + G + B> = 256 и R% 4 = 0 и G% 4 = 0 и B% 4 = 0) для каждой точки в другом наборе (colorTable). Ради этого вопроса игнорируйте, что первый набор разрабатывается программно, а не повторяется как сохраненный список, как второй набор.

Answer 1

Сначала вам нужно найти ближайшего соседа каждого элемента в другом наборе.

Чтобы сделать это эффективно, вам нужен алгоритм ближайший сосед . Лично я бы реализовал kd-tree только потому, что я делал это в прошлом в своем классе алгоритмов, и это было довольно просто. Другой жизнеспособной альтернативой является R-дерево .

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

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

При поиске пар ближайших соседей сохраняйте их в отсортированной структуре данных, которая имеет метод быстрого сложения и метод getMax, например heap , отсортированный по Евклидову дистанцию ​​.

Затем, как только вы закончите, просто попросите кучу максимум.

Время выполнения этого разбивается следующим образом:

N = размер меньшего набора
М = размер большего набора

• N * O (log M + 1) для всех проверок ближайшего соседа дерева kd.
• N * O (1) для вычисления евклидова расстояния перед добавлением его в кучу.
• N * O (log N) для добавления пар в кучу.
• O (1), чтобы получить окончательный ответ: D

Итак, в итоге весь алгоритм равен O (N * log M).

Если вам не важен порядок каждой пары, вы можете сэкономить немного времени и пространства, сохранив только найденный максимум.

* Отказ от ответственности: все это предполагает, что вы не будете использовать чрезвычайно большое количество измерений и что ваши элементы будут следовать в основном случайному распределению.

Answer 2

Может быть, я неправильно понимаю вопрос, но не проще ли будет просто поменять знак всех координат в одном наборе данных (т. Е. Умножить один набор координат на -1), а затем найти первого ближайшего соседа ( который был бы самым дальним соседом)? Вы можете использовать свой любимый алгоритм knn с k = 1.

Answer 3

Для каждой точки в наборе B найдите расстояние до ближайшего соседа в наборе A.

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

Answer 4

Чтобы сделать вещи более эффективными, рассмотрите возможность использования алгоритма Pigeonhole - сгруппируйте точки в вашем эталонном наборе (ваш colorTable) по их расположению в n-пространстве. Это позволяет эффективно находить ближайшего соседа без необходимости повторять все точки.

Например, если вы работали в двухмерном пространстве, разделите вашу плоскость на сетку 5 x 5, получая 25 квадратов с 25 группами точек.

В 3 клетках разделите куб на сетку 5 x 5 x 5, получив 125 кубов, каждый с набором точек.

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

Answer 5

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

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

Это nlog (n) для построения дерева и log (n) для одного поиска, поэтому все должно выполняться в nlog (n).

Answer 6

РЕДАКТИРОВАНИЕ : Я имел в виду nlog (n), где n - сумма размеров обоих наборов.

В наборе 1-Space I вы можете сделать что-то вроде этого (псевдокод)

Используйте такую ​​структуру

Struct Item {
    int value
    int setid
}

(1) Макс. Расстояние = 0
(2) Прочитать все наборы в структуры Item
(3) Создайте массив указателей на все предметы
(4) Сортировать массив указателей по Item-> value field структуры
(5) Пройдите массив от начала до конца, проверяя, отличается ли Item-> setid от предыдущего Item-> setid. if (SetIDs разные)
проверьте, больше ли это расстояние, чем Max Distance, если это так, установите MaxDistance на это расстояние

Возвращает максимальное расстояние.