Подскажите, пожалуйста, алгоритм со сложностью O(n ln(n)) для поиска пары ближайших точек (плоскость) в массиве. Было бы очень хорошо, если есть реализация на C# (но подойдет хотя бы псевдокод). p.s. На входе массив с точками (точки имеют координаты Х, У). На выходе - две точки, которые находятся на самом коротком расстоянии среди всех возможных вариантов. p.s.s. Фишка именно в сложности алгоритма: O(n ln(n)).
Ответ
Приведу выписку из своих конспектов по АиСД:
Отсортируем наш массив по координате x и y (На выходе получим два отсортированных массива; Время — O(nlogn)). Теперь мы запустим рекурсивную функцию, которая вернет нам две ближайшие точки.
В рекурсивной функции мы разделим массив точек на две части относительно медианы (за O(n)) и рекурсивно найдем в каждой из частей две ближайшие точки. Назовем кратчайшее расстояние, известное на данный момент, δ.
Осталось проверить, нету ли таких точек, которые лежат в разных половинах, и расстояние между ними короче, чем δ. Для этого рассмотрим любую точку и заметим вот что: если есть точка, расстояние до которой меньше, чем δ, она непременно должна лежать в прямоугольнике со сторонами δ на 2δ:
Но в таком прямоугольнике может уместиться не более шести точек, иначе расстояние между ними станет меньше δ и возникнет противоречие.
Тогда достаточно для каждой точки рассмотреть 6 следующих ее соседей в отсортированном по y массиве.
Время работы T[n]=2T[n/2]+O(n)=O(nlogn) по основной теореме о рекуррентных соотношениях.
Реализация на python
Комментариев нет:
Отправить комментарий