Loading AI tools
З Вікіпедії, вільної енциклопедії
Задача пошуку найближчої пари точок належить до задач обчислювальної геометрії: дано n точок в метричному просторі, знайти пару точок з найменшою відстанню між ними. Задача найближчої пари точок в евклідовій площині[1] була однією з перших геометричних задач, яка вирішувалась на початку систематичного вивчення обчислювальної складності геометричних алгоритмів.
«Наївний» алгоритм полягає в знаходженні відстаней між усіма парами точок в просторі даної розмірності і виборі мінімальної, це вимагає часу. Виявляється, що ця проблема може бути вирішена за часу в Евклідовому просторі або просторі Lp фіксованої розмірності d[2]. В алгебраїчному дереві рішень моделі обчислень, алгоритм складності є оптимальним. В обчислювальній моделі, яка передбачає, що функція знаходить результат за постійний час, кажуть, що проблема може бути вирішена за часу[3]. Якщо допускається рандомізація, з використання функції підлоги, то проблема може бути вирішена за часу[4][5].
Найближча пара точок може бути знайдена за час O(n2) з допомогою пошуку грубою силою. Щоб зробити це, можна обчислити відстані між усіма парами точок, потім вибрати пару з найменшою відстанню, як показано нижче.
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
Проблема може бути вирішена за часу, використовуючи рекурсивний підхід розділяй і володарюй, наприклад, наступним чином:
Виявляється, що 4-ий крок може бути виконаний за лінійний час. Знову ж, наївний підхід вимагає розрахунок відстаней для всіх пар зліва на право, тобто за квадратичний час. Ключове спостереження засноване на властивості розрідженості множини точок. Ми вже знаємо, що найближча пара точок не далі ніж . Таким чином, для кожної точки p ліворуч від розділової лінії, необхідно порівняти відстань до точки, які лежать у прямокутнику розмірів праворуч від розділової лінії, як показано на малюнку. Більш того, цей прямокутник може містити не більше шести точок з попарних відстаней принаймні . Таким чином, досить обчислити максимально 6n зліва направо відстаней на 4-му кроці. Рекурентне співвідношення для числа кроків може бути записане у вигляді , яке можна вирішити, використовуючи майстер-метод, щоб отримати .
Оскільки найближча пара точок визначає край у тріангуляції Делоне, і відповідає двом сусіднім коміркам на діаграмі Вороного, то найближча пара точок може бути визначена за лінійний час у разі використання однієї з цих структур. Обчислення чи то тріангуляції Делоне, чи діаграми Вороного займає часу. Ці підходи не є ефективними для розмірності , тоді як алгоритм розділяй і володарюй можна узагальнити і він буде виконуватись за час для будь-якого сталого значення d[джерело?].
Динамічна задача знаходження пари найближчих точок формулюється так:
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.