Найближча пара точок

Найближча пара точок може бути знайдена за час O(n²) з допомогою пошуку грубою силою. Щоб зробити це, можна обчислити відстані між усіма ${\displaystyle C_{n}^{2}=n(n-1)/2}$ парами точок, потім вибрати пару з найменшою відстанню, як показано нижче.

minDist = infinity
for i = 1 to length(P) - 1
 for j = i + 1 to length(P)
  let p = P[i], q = P[j]
  if dist(p, q) < minDist:
   minDist = dist(p, q)
   closestPair = (p, q)
return closestPair

Розділяй та володарюй: усічена смуга для перевірки

Проблема може бути вирішена за ${\displaystyle O(n\log {n})}$ часу, використовуючи рекурсивний підхід розділяй і володарюй, наприклад, наступним чином:

1. Сортування точок відповідно до їх x-координат.
2. Поділ множини точок на два рівні за розміром підмножини по вертикальній лінії ${\displaystyle x=x_{mid}}$.
3. Вирішити цю проблему рекурсивно в лівій і правій підмножині.
4. Знайти мінімальну відстань ${\displaystyle d_{LR_{min}}}$ серед множини пар точок, в яких одна точка лежить ліворуч від ділення по вертикалі, а інша точка праворуч.
5. Відповідь є мінімальним серед ${\displaystyle d_{L_{min}}}$, ${\displaystyle d_{R_{min}}}$ та ${\displaystyle d_{LR_{min}}}$.

Виявляється, що 4-ий крок може бути виконаний за лінійний час. Знову ж, наївний підхід вимагає розрахунок відстаней для всіх пар зліва на право, тобто за квадратичний час. Ключове спостереження засноване на властивості розрідженості множини точок. Ми вже знаємо, що найближча пара точок не далі ніж ${\displaystyle dist=\min(d_{L_{min}},d_{R_{min}})}$. Таким чином, для кожної точки p ліворуч від розділової лінії, необхідно порівняти відстань до точки, які лежать у прямокутнику розмірів ${\displaystyle (dist,2*dist)}$ праворуч від розділової лінії, як показано на малюнку. Більш того, цей прямокутник може містити не більше шести точок з попарних відстаней принаймні ${\displaystyle d_{R_{min}}}$. Таким чином, досить обчислити максимально 6n зліва направо відстаней на 4-му кроці. Рекурентне співвідношення для числа кроків може бути записане у вигляді ${\displaystyle T(n)=2*T\left({\frac {n}{2}}\right)+O(n)}$, яке можна вирішити, використовуючи майстер-метод, щоб отримати ${\displaystyle O(n\log {n})}$.

Оскільки найближча пара точок визначає край у тріангуляції Делоне, і відповідає двом сусіднім коміркам на діаграмі Вороного, то найближча пара точок може бути визначена за лінійний час у разі використання однієї з цих структур. Обчислення чи то тріангуляції Делоне, чи діаграми Вороного займає ${\displaystyle O(n\log {n})}$ часу. Ці підходи не є ефективними для розмірності ${\displaystyle d>2}$, тоді як алгоритм розділяй і володарюй можна узагальнити і він буде виконуватись за час ${\displaystyle O(n\log {n})}$ для будь-якого сталого значення d^{[джерело?]}.

Динамічна задача знаходження пари найближчих точок формулюється так:

• Для динамічної множини об'єктів, знайти алгоритми і структури даних для ефективного перерахунку найближчої пари об'єктів щоразу, коли об'єкти додаються або видаляються.

• Геоінформаційна система
• Пошук найближчого сусіда
• Задача про покриття множини