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

Задача

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

Обозначение

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

Решение

Воспользуемся идеей <<Разделяй-и-властвуй>>: разобьём наше множество по $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_{(n/2)}$ хотя бы на $d$. Более того, зафиксировав, скажем $p_1 \in P_1$, нет смысла рассматривать с ней в паре точки $p_2 \in P_2$, которые отличаются по $y$-координате также хотя бы на $d$.

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