Кратчайшее расстояние между точкой в ​​A и точкой в ​​B

Для двух наборов и каждый из которых содержит непересекающихся точек на плоскости, вычисляется кратчайшее расстояние между точкой в и точкой в , т. Е. .$A$$B$$n$$A$$B$$\min \space \{\mbox{ } \text{dist}(p, q) \mbox{ } | \mbox{ } p \in A \land q \in B \space \}$

Я не уверен, прав ли я, но эта проблема очень похожа на проблемы, которые можно решить с помощью линейного программирования в вычислительной геометрии. Однако сокращение до LP не является простым. Также моя проблема выглядит связанной с нахождением тончайшего условия между двумя наборами точек, которое, очевидно, может быть решено с помощью LP в $O(n)$ в 2-мерном пространстве.

У меня есть решение, которое может показаться немного запутанным, но должно быть более эффективным, чем наивный перебор:$\mathcal O(n^2)$

1. пусть будет ось между центрами масс и .A $v$$A$$B$
2. Сортируйте точки в и вдоль этой оси в порядке убывания и возрастания соответственно, получая последовательности , , ..., и , , ..., .B a 0 a 1 a n b 0 b 1 b $A$$B$$a_0$$a_1$$a_n$$b_0$$b_1$$b_n$

Остальное в псевдокоде, чтобы было понятнее:

d = infinity.
for j from 1 to n
    if (b_1 - a_j) along v > d then break endif
    for k from 1 to n
        if (b_k - a_j) along v > d then
            break
        else
            d = min( d , ||b_k - a_j|| )
        endif
    enddo
enddo

То есть, предварительно отсортировав точки вдоль , вы можете отфильтровать пары, которые никогда не будут находиться в пределах друг от друга, поскольку вдоль всегда будет,$v$$d$$b_k-a_j$$v$$\le \|b_k-a_j\|$

В худшем случае это все еще , но если и хорошо разделены, это должно быть намного быстрее, чем это, но не лучше, чем , что требуется для сортировки.$\mathcal O(n^2)$$A$$B$$\mathcal O(n\log n)$

Обновить

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

Что касается предложения использовать модифицированный алгоритм строчной развертки, хотя и интуитивно простое, я не уверен, что это в когда рассматриваются непересекающиеся множества. То же самое касается рандомизированного алгоритма Рабина.$\mathcal O(n\log n)$

Похоже, не так много литературы, посвященной проблеме ближайших пар в непересекающихся множествах, но я нашел это , которое не претендует на то, что находится под , и это , что не кажется делать какие-либо претензии о чем-либо.$\mathcal O(n^2)$

Вышеприведенный алгоритм можно рассматривать как вариант развертки плоскости, предложенный в первой статье (Шань, Чжан и Зальцберг), однако вместо использования оси и отсутствия сортировки используется ось между наборами и обходы множеств в порядке убывания / возрастания.$x$

Вы можете адаптировать алгоритм перестановки строк "ближайшая пара" , который является .$O(n \log n)$

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

Изменить: это на самом деле не просто (или даже возможно), как я описал. Смотрите комментарии для обсуждения.

Идея в таких задачах состоит в том, чтобы создать упорядоченную структуру из одного из наборов, которая позволяет эффективные запросы ближайшего соседа. Классическая статья, в которой была представлена ​​структура запроса O (log n) для произвольного измерения:

Шамос и Хой о решениях Вороного

С тех пор был создан ряд других космических перегородок, основанных на идеях тесселяций Делоне, и они также приводят к различным описаниям подпространственной развертки. Обратите внимание, что метод Вороного также подпадает под общее описание «разделяй и властвуй» из-за его плоского разбиения, которое делает этап построения O (n log n).

Итак, основное решение этой проблемы:

1. Возьмите набор A и постройте эффективную структуру запроса ближайшего соседа по вашему выбору. Этот шаг построения равен O (n log n) [см. Теорему 4].
2. Для каждого элемента в B, структура запроса A для ближайшего соседа. Каждый запрос O (log n) [см. Теорему 15, фиксированное измерение], поэтому общее время запроса для всех точек в B равно O (n log n).
3. Когда будет получен результат для ближайшей точки A к каждому B, поместите его в структуру, упорядоченную на расстоянии. Это O (log n) вставить каждый результат или O (n log n) для всех.
4. Когда все B были рассмотрены, вы можете быстро (O (1)) получить точку B в упорядоченной структуре с наименьшим соседним расстоянием до точки в A.

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

Я не уверен, прав ли я, но эта проблема очень похожа на проблемы, которые можно решить с помощью линейного программирования в вычислительной геометрии. Однако сокращение до LP не является простым. Также моя проблема выглядит связанной с нахождением самого тонкого условия между двумя наборами точек, которое, очевидно, может быть решено с помощью LP в 2-мерном пространстве.

Нижняя граница для этой задачи - в алгебраической модели дерева решений. Я приведу примерный набросок его доказательства здесь.$O(n*\log{n})$

Мы сократим случай проблемы отличимости элементов E до C.

• Ввод в E: $S = \{a_1, a_2, a_3,...,a_n\}$
• Пусть > 0 - небольшая дробь$\epsilon$
• A = ,$\{(a_i,0) : 1 \leq i \leq n\}$$B = \{(a_i + \epsilon) : 1 \leq i \leq n\}$
• Теперь, если мы можем найти кратчайшее расстояние (d) между множествами A и B. Мы можем решить проблему отличимости элементов в дополнительное время следующим образом $O(n)$
  • Множество имеет дубликат тогда и только тогда, когда d =$S$$\epsilon$

Мы знаем, что нижняя граница времени выполнения для решения проблемы отличимости элементов . Следовательно, при уменьшении нижняя граница также относится к нашей проблеме.$O(n*\log{n})$