![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/3/37/Closest_pair_of_points.svg/languk-640px-Closest_pair_of_points.svg.png&w=640&q=50)
Найближча пара точок
З Вікіпедії, безкоштовно encyclopedia
Задача пошуку найближчої пари точок належить до задач обчислювальної геометрії: дано n точок в метричному просторі, знайти пару точок з найменшою відстанню між ними. Задача найближчої пари точок в евклідовій площині[1] була однією з перших геометричних задач, яка вирішувалась на початку систематичного вивчення обчислювальної складності геометричних алгоритмів.
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/3/37/Closest_pair_of_points.svg/220px-Closest_pair_of_points.svg.png)
«Наївний» алгоритм полягає в знаходженні відстаней між усіма парами точок в просторі даної розмірності і виборі мінімальної, це вимагає часу. Виявляється, що ця проблема може бути вирішена за
часу в Евклідовому просторі або просторі Lp фіксованої розмірності d[2]. В алгебраїчному дереві рішень моделі обчислень, алгоритм складності
є оптимальним. В обчислювальній моделі, яка передбачає, що функція знаходить результат за постійний час, кажуть, що проблема може бути вирішена за
часу[3]. Якщо допускається рандомізація, з використання функції підлоги, то проблема може бути вирішена за
часу[4][5].