7.5. Задача «Пара ближайших точек»

Ваша задача — найти ближайшую пару точек из заданного множества.

В компьютерных графике и зрении есть множество вариантов применения этой задачи из вычислительной геометрии. Примитивный алгоритм с квадратичным временем выполнения делает итерации, проходя через все пары точек, чтобы найти ближайшие друг к другу. Ваша цель — спроектировать алгоритм «разделяй и властвуй», время выполнения которого составит $O(n\log n)$.

Чтобы решить эту задачу за время $O(n\log n)$, разобьём с помощью правильно подобранной вертикальной линии данные $n$ точек пополам — множества $S_1$ и $S_2$ размера $\frac{n}{2}$. Ради простоты предположим, что все координаты $x$ для данных точек различные и количество точек чётное. С помощью двух рекурсивных вызовов с параметрами $S_1$ и $S_2$ мы находим минимальные расстояния $d_1$ и $d_2$ в этих поднаборах. Пусть $d=\min{d_1, d_2}$.

Остаётся проверить, существуют ли такие точки $p_1 \in S_1$ и $p_2 \in S_2$, при которых расстояние между ними меньше $d$. Мы не можем себе позволить проверять все возможные такие пары, так как их $\frac{n}{2} \cdot \frac{n}{2}=\Theta(n^2)$. Для более быстрой проверки мы отбросим все точки из $S_1$ и $S_2$, расстояние которых от центральной линии по $x$ больше, чем $d$. Таким образом, мы сосредотачиваемся на следующей полосе:

💡 Остановитесь и подумайте:
Почему мы можем сузиться до этой полосы?

Теперь отсортируем точки из полосы по координатам $y$ и обозначим получившийся отсортированный список $P=[p_0,\dotsc, p_{k-1}]$. Оказывается, что если $|i-j|>7$, то расстояние между точками $p_i$ и $p_j$ однозначно будет больше $d$. Упражнение ниже это демонстрирует.

✒️ Упражнение:
Разделите полосу на $d \times d$ квадратов, как показано ниже, и продемонстрируйте, что каждый из таких квадратов содержит максимум четыре точки ввода.

Это приводит к следующему алгоритму. Сначала мы сортируем данные нам $n$ точек по их координатам $x$, затем делим получившийся отсортированный список на две половины $S_1$ и $S_2$ размера $\frac{n}{2}$. Находим минимальные расстояния $d_1$ и $d_2$ с помощью рекурсивных вызовов для каждого из наборов $S_1$ и $S_2$. Пусть $d=\min{d_1,d_2}$. Тем не менее наша работа ещё не закончена, потому что нам также нужно найти минимальное расстояние между точками из разных наборов (то есть точкой из $S_1$ и точкой из $S_2$) и проверить, ниже ли это расстояние, чем $d$. Чтобы в этом убедиться, мы отфильтруем изначальный набор и оставим только точки с дистанцией по $x$ до средней линии, не превышающей $d$. После этого мы сортируем набор точек в получившейся линии по координатам $y$ и сканируем получившийся список. Вычислим расстояние от каждой точки до семи последующих точек списка и вычислим $d'$ — минимальное расстояние, которое нам встретилось во время сканирования. Затем выведем $\min{d,d'}$.

Время выполнения алгоритма соответствует рекуррентному соотношению. $$ T(n)=2 \cdot T\left(\frac{n}{2}\right) + O(n \log n) , $$

$O(n\log n)$ — результат сортировки точек в полосе по координате $y$ при каждой итерации.

✒️ Упражнение:
Проанализируйте рекурсивное дерево алгоритма и докажите, что $T(n)=O(n\log^2 n)$.

✒️ Упражнение:
Продемонстрируйте, как избежать сортировки при каждом рекурсивном вызове и понизить время выполнения до $O(n \log n)$.

• Формат ввода: Первая строка содержит $n$ точек. Каждая из следующих $n$ строк определяет точку $(x_i,y_i)$.
• Формат вывода: Минимальное расстояние.
• Ограничения: $2 \le n \le 10^5$; $-10^9 \le x_i,y_i \le 10^9$ — целые числа.
• Примеры

Пример 1

Пример 2

• Во втором примере самое маленькое расстояние — $\sqrt{2}$. Есть две пары точек на этом расстоянии. Ниже они выделены голубым и красным: $(-1,-1)$ и $(-2,-2)$; $(-2,4)$ и $(-1,3)$.

Помните, что расстояние между точками $(x_1,y_1)$ и $(x_2,y_2)$ равно $\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$. Так, хотя ввод и содержит только целые числа, ответ не обязательно будет целым числом, и потому вам нужно обратить внимание на точность при выводе результатов. Абсолютное значение разницы между ответом вашей программы и оптимальным значением не должно превышать $10^{-3}$. Для этого ваш ответ должен содержать не меньше четырех цифр в дробной части. Иначе даже правильно вычисленный результат может не пройти нашу систему проверки из-за ошибок при округлении.

💡 Совет: по возможности старайтесь избегать использования чисел с плавающей дробной частью, при необходимости используйте встроенные алгоритмы для сортировки.