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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Найближча пара зафарбована в червоний колір

Задача пошуку найближчої пари точок відноситься до задач обчислювальної геометрії: дано n точок в метричному просторі, знайти пару точок з найменшою відстанню між ними. Задача найближчої пари точок в евклідовій площині[1] була однією з перших геометричних задач, яка вирішувалась на початку систематичного вивчення обчислювальної складності геометричних алгоритмів.

«Наївний» алгоритм полягає в знаходженні відстаней між усіма парами точок в просторі даної розмірності і виборі мінімальної, це вимагає часу. Виявляється, що ця проблема може бути вирішена за часу в Евклідовому просторі або просторі Lp фіксованої розмірності d[2]. В алгебраїчному дереві рішень моделі обчислень[en], алгоритм складності є оптимальним. В обчислювальній моделі, яка передбачає, що функція знаходить результат за постійний час, кажуть, що проблема може бути вирішена за часу[3]. Якщо допускається рандомізація, з використання функції підлоги, то проблема може бути вирішена за часу[4][5].

Алгоритм перебору[ред.ред. код]

Найближча пара точок може бути знайдена в O(n2) час за допомогою виконання пошуку грубою силою[en]. Щоб зробити це, можна обчислити відстані між усіма 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

Планарний випадок[ред.ред. код]

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

  1. Сортування точок відповідно до їх x-координат.
  2. Поділ множини точок на два рівні за розміром підмножини по вертикальній лінії .
  3. Вирішити цю проблему рекурсивно в лівій і правій підмножині.
  4. Знайти мінімальну відстань серед множини пар точок, в яких одна точка лежить ліворуч від ділення по вертикалі, а інша точка праворуч.
  5. Відповідь є мінімальним серед , та .
Розділяй та володарюй

Виявляється, що 4-ий крок може бути виконаний за лінійний час. Знову ж, наївний підхід вимагає розрахунок відстаней для всіх пар зліва на право, тобто за квадратичний час. Ключове спостереження засноване на властивості розрідженості множини точок. Ми вже знаємо, що найближча пара точок не далі ніж . Таким чином, для кожної точки p ліворуч від розділової лінії, необхідно порівняти відстань до точки, які лежать у прямокутнику розмірів праворуч від розділової лінії, як показано на малюнку. Більш того, цей прямокутник може містити не більше шести точок з попарних відстаней принаймні . Таким чином, досить обчислити максимально 6n зліва направо відстань на 4-му кроці. Рекурентне співвідношення для числа кроків може бути записане у вигляді , які можна вирішити, використовуючи метод майстра, щоб отримати .

Оскільки найближча пара точок визначає край у тріангуляції Делона, і відповідає двом сусіднім коміркам на діаграмі Вороного, то найближча пара точок може бути визначена за лінійний час у разі використання однієї з цих структур. Обчислення або тріангуляції Делоне, або діаграми Вороного займає часу. Ці підходи не є ефективними для розмірності , тоді як алгоритм розділяй і володарюй може бути узагальнено застосовний за часу для будь-якого постійного значення d.

Динамічна задача знаходження пари найближчих точок[ред.ред. код]

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

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

Див. також[ред.ред. код]

Посилання[ред.ред. код]

Примітки[ред.ред. код]

  1. Шамос, Майкл Ян; Хой, Ден (1975). Closest-point problems. 16-й річний симпозіум у Фонді комп'ютерних наук IEEE. с. 151—162. doi:10.1109/SFCS.1975.8. 
  2. Кларксон, К. Л. (1983). Fast algorithms for the all nearest neighbors problem. FOCS. 
  3. Фортуна, С.; Гопкрофт, Дж. Є. (1979). A note on Rabin's nearest-neighbor algorithm. Information Processing Letters 8 (1). с. 20—23. 
  4. Хуллер, С.; Матіас, І. (1995). A simple randomized sieve algorithm for the closest-pair problem. Inf. Comput. 118 (1). с. 34—37. 
  5. Ліптон, Річард (24 вересня 2011). Rabin Flips a Coin.