Поиск двух ближайших точек

Задача

Даны $n$ точек на плоскости, необходимо найти $2$ из них, расстояние между которыми минимально.

Обозначения

• $P_{(i)}$ означает $i$-ую точку множества $P$, отсортированного по $x$-координате.
• $p^{(y)}$ означает $y$-координату точки $p$.

Идеи решения

Воспользуемся идеей <<Разделяй-и-властвуй>>: разобьём наше множество по $x$-координате точек на два: $P_1$ и $P_2$ $|P_{i}| = \frac{n}{2}$ в каждом, рекурсивно найдём ответ в каждом из них: $d_1$ и $d_2$, а после этого попытаемся найти пару точек $p_1 \in P_1$ и $p_2 \in P_2$ таких что $\rho(p_1, p_2) < min(d_1, d_2) = d$.

Будем перебирать только те пары точек из обоих множеств, которые потенциально могут дать результат, лучше чем $d$. Заметим, что это означает, что нет смысла рассматривать точки, чья $x$-координата отличается от $x$-координаты $P_{(\frac{n}{2})}$ хотя бы на $d$. Более того, зафиксировав, скажем $p_1 \in P_1$, нет смысла рассматривать с ней в паре точки $p_2 \in P_2$, которые отличаются по $y$-координате также хотя бы на $d$.

Таким образом, для каждой точки из $P_1$ имеет смысл рассматривать только те точки из $P_2$, которые лежат в прямоугольнике размера $2d \times 2d$. В дальнейшем мы докажем, что количество таких точек не превосходит некоторой константы, из чего следует, что число потенциально улучшающих ответ пар (на шаге слияния) не более чем линейно по $n$.

Почему количество интересующих нас пар точек линейно по $n$?

Пусть $p_1 \in P_1$. Как мы уже поняли, все точки $p_2 \in P_2$, которые могут образовывать интересную нам пару с $p_1$ лежат в квадрате $2d \times 2d$. Разобьём его на 16 квадратов размера $\frac{d}{2}$ каждый. Заметим, что тогда в каждом из получившихся квадратиков не более одной интересующей нас точки, иначе бы в $P_2$ нашлись 2 точки, расстояние между которыми не больше $\sqrt(2) \times \frac{d}{2} = \frac{d}{\sqrt{2}} < d \leq d_2$, чего быть точно не может, иначе бы рекурсивный вызов в $P_2$ нашёл бы это (меньшее, чем то, что он нашёл) расстояние.

Следовательность, для каждой точки из $P_1$ существует не более чем константа потенциальных пар, а значит общее число потенциальных пар линейно по $n$.

Детали реализации

Предварительная сортировка по $x$-координате

Заметим, что на каждом шаге рекурсии мы разделяем текущее множество точек по $x$-координате его медианы. Чтобы не сортировать каждый раз, отсортируем все точки вначале и будем передавать в рекурсию индексы множества точек, с которым мы сейчас работаем.

Внутренняя сортировка по $y$-координате

Чтобы перебирать только те пары точек, которые нам интересны, хочется иметь точки внутри обеих полос шириной $d$ (по обе стороны от $P_{(\frac{n}{2})})$ отсортированными по $y$. Для этого можно потребовать, чтобы рекурсивный вызов не только возвращал ответ $d_i, i \in \{ 1, 2 \}$ в подзадаче, но и два (отсортированных по $y$-координате)списка точек, которые находятся на расстоянии $d_i$ от границ множества, на котором мы вызываемся (списка 2, потому что границ тоже 2).

Тогда на стадии слияния нам нужно будет рассмотреть 2 из 4 полученных из рекурсии полос (те, которые находятся по бокам от разделяющей линии), а наверх передать те точки из оставшихся (боковых) полос, которые отстоят от границ не дальше, чем ответ, полученный после объединения (ведь мы вполне могли найти расстояние меньшее, чем полученное в рекурсивных вызовах).

2 указателя

Теперь, имея 2 списка точек в средних полосах, отсортированных по $y$-координате, нам достаточно пройтись 2 указателями, так чтобы расстояние между точками, на которые смотрят указатели, не превышало $min(d_1, d_2)=d$. Заметим, что для каждой новой точки в $P_1$ (назовём её, внезапно, $p_1$) нам необязательно каждый раз просматривать все точки $P_2$ заново, достаточно откатить второй указатель наз до тех пор, пока он не начнёт указывать на точку из $P_2$, $y$-координата которой меньше (мы считаем, что оба указателя идут по полосам снизу-вверх) $p_1^{(y)} - d$ (либо пока указатель не упрётся в начало списка).

Обрубаем рекурсию

Заметим, что нам необязательно опускаться до самого конца в дереве рекурсии, чтобы получить ответ. Можно, например, увидев, что число точек на каком-то этапе меньше, скажем, 10, просто перебрать все пары точек и найти наилучшую, после чего отдать наверх по рекурсии все интересующие нас массивы.

Время работы

Оценим время работы нашего алгоритма:

$$ T(n) = 2T(\frac{n}{2}) + \underbrace{\Theta(n)}_{\text{проход двумя указателями}} + \underbrace{\Theta(n)}_{\text{удаление из боковых полос лишних точек}} = 2T(\frac{n}{2}) + \Theta(n) \implies T(n) = \Theta(n\log(n)) $$

---

Автор конспекта: Александр Гришутин

По всем вопросам пишите в telegram @rationalex