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

Question

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

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

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

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

Answer 1

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

Таким образом, вы можете составить два списка - членов A и их ближайшего соседа в B и членов B и их ближайшего соседа в A - за 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).

Answer 2

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

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

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

Answer 3

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

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

Answer 4

• BSP / Octree / Kd-дерево (спасибо, TZHX)
• Кривые заполнения пространства (например, с использованием кривой Гильберта );Google дает много релевантных результатов для поиска пары.