Алгоритм поиска пары ближайших точек

#алгоритм #геометрия

Подскажите, пожалуйста, алгоритм со сложностью O(n ln(n)) для поиска пары ближайших
точек (плоскость) в массиве. Было бы очень хорошо, если есть реализация на C# (но подойдет
хотя бы псевдокод).
p.s. На входе массив с точками (точки имеют координаты Х, У). На выходе - две точки,
которые находятся на самом коротком расстоянии среди всех возможных вариантов.
p.s.s. Фишка именно в сложности алгоритма: O(n ln(n)).
    

Ответы

Ответ 1

Приведу выписку из своих конспектов по АиСД:

Отсортируем наш массив по координате x и y (На выходе получим два отсортированных
массива; Время — O(nlogn)). Теперь мы запустим рекурсивную функцию, которая вернет
нам две ближайшие точки.

В рекурсивной функции мы разделим массив точек на две части относительно медианы
(за O(n)) и рекурсивно найдем в каждой из частей две ближайшие точки. Назовем кратчайшее
расстояние, известное на данный момент, δ.



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



Но в таком прямоугольнике может уместиться не более шести точек, иначе расстояние
между ними станет меньше δ и возникнет противоречие.

Тогда достаточно для каждой точки рассмотреть 6 следующих ее соседей в отсортированном
по y массиве.

Время работы T[n]=2T[n/2]+O(n)=O(nlogn) по основной теореме о рекуррентных соотношениях.

Реализация на python