Конспект: ближайшая пара точек

Понятия

Полоса - зона шириной 2d вокруг вертикального разреза, где d - меньший из ответов двух половин. Только там могут лежать пары, разрезанные границей.

Что унести

1. отсортировать точки по x ОДИН раз, до всей рекурсии
2. разделить пополам, найти d_left и d_right, взять d = min(d_left, d_right)
3. собрать полосу: точки с (x − x_разреза)² < d²
4. отсортировать полосу по y
5. для каждой точки полосы проверять следующие, ПОКА (y_j − y_i)² < d²
6. ответ = минимум из d и найденного в полосе

Почему полосы достаточно: если пара разрезана границей и расстояние в ней меньше d, то обе её точки ближе d к границе.

Почему в полосе мало соседей. Опасные точки лежат в прямоугольнике 2d × d; он разбивается на восемь квадратов со стороной d/2. Каждый квадрат целиком в одной половине, его диагональ (d/2)·√2 ≈ 0.707·d меньше d, а внутри половины расстояния не меньше d - значит в квадрате не больше одной точки. Итого не больше восьми точек, минус сама наша: семь. Константа не зависит ни от n, ни от плотности. В коде семёрку не зашивают - пишут обрыв по (y_j − y_i)² < d².

Все сравнения идут по КВАДРАТАМ расстояний: корень не нужен ни для сравнения, ни для ответа, а на целых координатах арифметика остаётся точной.

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

Где ломается: в k измерениях ограничить удаётся только две оси из k (полоса и порядок сканирования), и доказательство про «семь соседей» не переносится вовсе. Там берут сетку с ребром d и просматривают 3^k клеток на точку - проклятие размерности; там берут сетку, kd-дерево (до десятка измерений) или приближённый поиск соседей. Рандомизированный алгоритм даёт ОЖИДАЕМОЕ O(n), но не гарантию.

Тихие ошибки: забыть про разрезанные пары (ответ завышен молча); сортировать по x внутри рекурсии; строить полосу от большего из двух минимумов; не обрывать цикл по y; переносить константу 7 в трёхмерие.

Куда это ведёт

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