Учитывая два (больших) набора точек, как я могу эффективно находить пары, которые являются ближайшими друг к другу?

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

Учитывая множество точек A и множество точек B в евклидовом пространстве, найдите все пары (a, b) такие, что b является ближайшей точкой в ​​B к a, а a - ближайшая точка в к b.

Множества A и B имеют примерно одинаковый размер, и этот размер будет называться N. Для моей конкретной задачи N составляет около 250 000.

Решение грубой силы состоит в том, чтобы сравнивать каждую точку с каждой другой точкой, которая имеет квадратичную временную сложность. Есть ли более эффективный алгоритм для этого?

Ответы

Ответ 1

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

Таким образом, вы можете создать два списка: членов A и их ближайшего соседа в B и членов B и их ближайшего соседа в - в O (N log N) времени. Затем вы можете сравнить списки, чтобы увидеть, какие пары совпадают. Сделано наивно, что O (N ^ 2), хотя вы можете подумать о способе сделать это быстрее.

[править] Вы меня задумали; здесь моя вторая мысль:

for(a in A)
    b := nearest(B, a)
    if a = nearest(A, b)
        add (a, b) to results
    end if
end for

function nearest(X, y)
    return nearest member of set X to point y
end function

По моим подсчетам, что O (N log N).

Ответ 2

Извините за то, что выбрал довольно старый поток, но я просто хотел добавить решение, которое я нашел в своем учебнике для класса Algorithm Design:

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

  • Сортировка всех точек в соответствии с X-значением.
  • Разделить весь набор на две равные части.
  • Считайте каждую половину и выберите минимальное расстояние (d)
  • Найдите правую часть (p) в левой половине и проверьте расстояние для всех точек между p_x и p_x + d, если какое-либо из этих расстояний меньше d, то есть d для возврата, в противном случае верните d.

Ответ 3

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

Я полагаю, что для n-мерного множества точек ближайшая точка между двумя множествами может быть найдена путем нахождения ближайшей точки к началу множества разностей. Вы можете найти статью Филиппа Вулфа из Bell Labs, где он излагает алгоритм. Вы можете думать об этом, взяв случайную точку в множестве A, найдя ближайшую точку в множестве B, затем найдя ближайшую точку к точке в множестве B и т.д. http://link.springer.com/article/10.1007%2FBF01580381