4

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

1 ответ 1

9

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

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

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

разбиение

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

квадрат

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

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

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

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

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.