Ближайшая пара точек: деление, которое упирается в границу

Если ты знаешь схему «раздели по x, возьми меньшее из двух, проверь полосу» и понимаешь, зачем полоса нужна, листай до «Теперь сам».

Как думаешь, достаточно ли двух половин

Разрежем точки вертикальной линией пополам: слева n/2, справа n/2. Рекурсивно найдём ближайшую пару в каждой половине; пусть слева минимум 7, справа 5. Ответ - 5?

Нет. Две точки могут лежать по разные стороны от линии, почти вплотную к ней - и расстояние между ними окажется 2. Ни левая рекурсия, ни правая эту пару не увидят: каждая из них смотрит только на свою половину. Значит объединение здесь - не «взять минимум», а отдельная работа.

На что это похоже

Поиск двух самых похожих людей в очереди, разбитой пополам турникетом. Внутри каждой части сравнить можно, а вот пары «последний до турникета и первый после» видны только если специально посмотреть на стык. И чем лучше ответы внутри частей, тем УЖЕ зона у стыка, в которую вообще стоит смотреть.

Механизм: три случая и полоса

1. отсортировать точки по x (один раз, перед всей рекурсией)
2. если точек не больше трёх - перебрать все пары и вернуть минимум (база рекурсии)
3. разделить отсортированный массив ПО СЕРЕДИНЕ: первые n/2 точек - левая половина,
   остальные - правая; линия разреза проходит по x серединной точки.
   Делим именно по индексу, а не по значению x: при совпадающих x деление
   «по координате» оставило бы половину пустой и рекурсия не закончилась бы
4. d_left  = closest(левая)
   d_right = closest(правая)
   d = min(d_left, d_right)
5. ПОЛОСА: точки, у которых |x − x_разреза| < d
   отсортировать полосу по y
   для каждой точки полосы проверить следующие, пока разница по y < d
6. ответ = минимум из d и найденного в полосе

Три случая, которые покрывает эта схема:

обе точки слева   → нашла левая рекурсия
обе точки справа  → нашла правая рекурсия
по разные стороны → ОБЕ ближе d к разрезу, значит обе в полосе

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

цена:  T(n) = 2·T(n/2) + (сортировка полосы + линейный проход)
       если полосу сортировать заново:  T(n) = 2·T(n/2) + n·log n  →  Θ(n·log² n)
       если поддерживать порядок по y слиянием:  T(n) = 2·T(n/2) + n  →  Θ(n·log n)

Правило

Ближайшая пара делением пополам: отсортировать точки по x ОДИН раз, рекурсивно решить половины, взять d - меньшее из двух ответов, и отдельно проверить пары, разрезанные границей. Такие пары обязаны лежать в полосе шириной 2d вокруг разреза: если расстояние меньше d, то каждая точка ближе d к границе. Полосу сортируют по y и для каждой точки смотрят следующие, пока разница по y меньше d. Сортировка полосы на каждом уровне даёт Θ(n·log² n), поддержание порядка по y слиянием - честные Θ(n·log n). Расстояния сравнивают КВАДРАТАМИ: для сравнения корень не нужен, и на целых координатах арифметика остаётся точной.

Разбор: почему без полосы ответ неверен

Возьмём восемь точек и разрежем их по x = 50.

слева:  (10, 10)  (20, 80)  (30, 30)  (49, 55)
справа: (51, 57)  (70, 20)  (80, 90)  (95, 45)

ближайшая слева:   (10,10)-(30,30)  →  d² = 400 + 400 = 800
ближайшая справа:  (70,20)-(95,45)  →  d² = 625 + 625 = 1250
минимум из двух:   800

а теперь пара через разрез:
(49, 55)-(51, 57)  →  d² = 4 + 4 = 8

Восемь против восьмисот - ответ, который обе рекурсии в упор не видят. Проверим, что полоса его поймает. Здесь один раз возьмём корень для наглядности: d = √800 ≈ 28.3, полоса - точки с |x − 50| < 28.3, то есть x от 21.7 до 78.3. В коде корень не берут - там то же условие пишут как (x − 50)² < 800, и никакой потери точности на целых координатах не возникает. В неё попадают (30,30), (49,55), (51,57), (70,20) - четыре точки из восьми. Отсортировав их по y, получим (70,20), (30,30), (49,55), (51,57), и пара (49,55)-(51,57) стоит рядом.

Заметь, что в полосу попали точки И СЛЕВА, И СПРАВА - иначе смысла бы не было: мы ищем именно разрезанные пары.

Разбор: почему полоса узкая, а не «все точки»

Может показаться, что полоса - это просто «ещё один перебор», только с лишним условием. Разница в том, что её ширина зависит от УЖЕ НАЙДЕННОГО ответа, и чем лучше ответ, тем меньше работы.

если точки распределены равномерно в квадрате n × n,
а минимальное расстояние d мало,
то в полосе шириной 2d оказывается примерно n · (2d / ширина квадрата) точек

Крайний случай, который стоит держать в голове: все точки лежат НА одной вертикальной прямой, близко друг к другу. Тогда в полосу попадут все n точек, и перебор внутри полосы был бы квадратичным. Спасает второе условие - обрыв по разнице y: как только по вертикали расстояние стало не меньше d, дальше смотреть незачем. Сколько точек может оказаться «в пределах d по вертикали» - вопрос следующего урока, и ответ там на удивление мал: не больше семи.

Без обрыва по y алгоритм остаётся верным, но теряет всю асимптотику: T(n) = 2·T(n/2) + n², то есть Θ(n²) - ровно случай «корень тяжелее» из первой главы раздела.

Что ломается без этого

Первое: брать минимум из двух половин и забыть про разрезанные пары - ответ будет завышен, причём молча и не на всех входах. Второе: сортировать точки по x внутри рекурсии, а не один раз снаружи: добавится лишний log n на каждом уровне. Третье: путать «шире» и «уже»: полоса с d БОЛЬШИМ, чем нужно (например с минимумом только левой половины), оставляет ответ верным и лишь добавляет работы, а полоса уже d молча теряет разрезанные пары и делает ответ неверным. Четвёртое: сравнивать расстояния, а не их квадраты: корень стоит дорого и портит точность на целых координатах. Пятое: не обрывать внутренний цикл по разнице y - алгоритм останется верным и станет квадратичным.

Зачем это в работе

Ближайшая пара - это не про геометрию ради геометрии. Тот же вопрос звучит как «найти два почти одинаковых документа», «обнаружить два объекта на курсе столкновения», «найти дубликаты записей по координатам», «выделить кластеры в облаке точек». В двумерии описанный алгоритм - классика; в пространстве большей размерности он вырождается (полоса перестаёт быть узкой), и там работают другие структуры: kd-деревья, сетки, хеширование, чувствительное к близости. Но приём «раздели, реши, и отдельно разберись с тем, что попало на границу» переносится прямо: так устроены пространственные индексы в базах данных и обнаружение столкновений в играх и симуляторах.

Теперь сам

Слева ближайшая пара даёт d² = 100, справа d² = 64, разрез идёт по x = 40. Какой ширины полосу надо проверить и какие из этих точек в неё попадут: (28, 5), (33, 40), (39, 12), (41, 60), (47, 12), (52, 33)?