Почему в полосе мало соседей: восемь клеток

Если ты умеешь доказать оценку «не больше семи соседей» разбиением на квадраты и понимаешь, откуда берётся линейность объединения, листай до «Теперь сам».

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

В полосе шириной 2d лежат, скажем, двести точек, отсортированных по y. Для первой из них надо найти, нет ли рядом точки ближе d.

Кандидаты - те, у кого разница по y меньше d. Их может быть и десять, и сто девяносто девять: полоса-то узкая по x, но по y она длинная, и ничто не мешает набить её точками. Вопрос: сколько кандидатов может оказаться ОДНОВРЕМЕННО близко и по y, и вообще?

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

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

Механизм: разбиение на восемь квадратов

точка p лежит в полосе; опасны точки, у которых:
    разница по y меньше d   (иначе расстояние уже >= d)
    x внутри полосы          (ширина полосы 2d: по d в каждую сторону от разреза)

значит все опасные точки лежат в прямоугольнике  2d (по x) × d (по y),
считая только точки ДАЛЬШЕ p по y (с большим y) - те, что идут следом в отсортированном
списке; пары с меньшим y уже проверены, когда мы стояли в той точке

площадь прямоугольника: 2d × d
квадрат со стороной d/2 → их ровно 8
диагональ квадрата: (d/2)·√2 ≈ 0.707·d  <  d

Правило

В полосе для каждой точки достаточно проверить СЕМЬ следующих по y. Доказательство: опасные точки лежат в прямоугольнике 2d × d, который разбивается на восемь квадратов со стороной d/2; каждый квадрат целиком лежит в одной половине, диагональ квадрата 0.707·d меньше d, а внутри половины минимальное расстояние равно d - значит в квадрате не больше одной точки. Итого не больше восьми точек, одна из них наша. Поэтому проход по полосе линеен, и вся схема даёт Θ(n·log n) при поддержании порядка по y слиянием (или Θ(n·log² n) с пересортировкой).

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

Проверим утверждение на пальцах. Пусть d = 10, разрез по x = 0, и точка p = (−3, 0).

опасный прямоугольник: x от −10 до 10, y от 0 до 10

разобьём на квадраты 5 × 5 (границу относим к ЛЕВОМУ и НИЖНЕМУ квадрату,
чтобы каждая точка попала ровно в один):
    левая половина:  x ∈ [−10,−5) и [−5, 0),  y ∈ [0,5) и [5,10]   →  4 квадрата
    правая половина: x ∈ [0, 5) и [5, 10],    y ∈ [0,5) и [5,10]   →  4 квадрата

в каждом квадрате диагональ = 5·√2 ≈ 7.07 < 10

Почему в квадрате не больше одной точки: обе точки квадрата лежали бы в ОДНОЙ половине (квадрат границу не пересекает), а внутри половины ближайшая пара уже найдена и равна d = 10. Если бы в квадрате оказались две точки, расстояние между ними было бы не больше 7.07 - меньше 10, то есть рекурсия для этой половины нашла бы пару ближе, чем нашла. Противоречие.

Значит точек в прямоугольнике не больше восьми, и, отбросив саму p, проверять надо не больше семи. Число 7 (иногда пишут 8) - это КОНСТАНТА, не зависящая ни от n, ни от плотности точек. Именно она превращает проход по полосе в линейный.

Разбор: откуда берётся n·log n, а откуда n·log² n

Разница - в том, как получается полоса, отсортированная по y.

вариант 1: на каждом уровне сортировать полосу заново
    T(n) = 2·T(n/2) + n·log n
    здесь f(n) = n·log n - это ровно n^(log₂ 2) · log n, то есть случай
    «поровну по уровням» с ЛОГАРИФМИЧЕСКИМ множителем: каждый уровень весит
    одинаково, и добавляется ещё один log n
    ответ Θ(n·log² n)

вариант 2: рекурсия возвращает свои точки, УЖЕ отсортированные по y,
           а родитель сливает два отсортированных списка за линию
    T(n) = 2·T(n/2) + n
    ответ Θ(n·log n)

Второй вариант - это ровно сортировка слиянием, встроенная в геометрический алгоритм: тот же приём, что и в разделе про сортировки, только слияние здесь попутное. Практическая разница между log n и log² n на миллионе точек - примерно в двадцать раз, и на этом размере она уже заметна.

Замер на движке курса (задача этой главы): 250 точек, деление пополам с пересортировкой полосы - 19 тысяч шагов, полный перебор - 188 тысяч. Почти в десять раз, и это при том, что константа у перебора минимальная, а у деления есть и рекурсия, и сортировки.

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

Первое: проверять в полосе ВСЕ пары - верно, но квадратично; вся оценка держится на обрыве по y. Второе: считать, что «семь» надо зашивать в код как for k in range(7): правильнее писать обрыв по условию (y_j − y_i)² < d², а семёрка - это следствие, которое гарантирует, что цикл не затянется. Третье: строить полосу от d, взятого до рекурсии, а не после: ширина должна быть от УЖЕ найденного минимума, иначе полоса окажется шире нужного. Четвёртое: раскладывать полосу на «левые» и «правые» и сравнивать их между собой: для ОТВЕТА это не ошибка (разрезанная пара по определению состоит из левой и правой точки), но код усложняется на ровном месте, а оценка «семь соседей» перестаёт из него читаться - она доказана для общего списка, отсортированного по y. Пятое: переносить оценку «не больше семи» в трёхмерие: там ограничены уже не все оси (полоса даёт одну, порядок сканирования - вторую, а третья ничем не связана), поэтому доказательство не переносится вовсе - о многомерии речь в следующем уроке.

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

Само число 7 применяется редко, а вот приём доказательства - постоянно. «Сколько объектов может одновременно оказаться рядом, если они не могут быть слишком близко друг к другу» - это вопрос из обнаружения столкновений, из разметки карт, из планирования радиочастот, из алгоритмов кластеризации. Ответ всегда получается одинаково: накрыть область ячейками такого размера, чтобы в ячейку помещался максимум один объект, и посчитать ячейки. Эта же идея лежит в основе пространственного хеширования: разбить пространство на сетку с шагом d и смотреть только соседние клетки - тогда для равномерных данных поиск соседей становится почти константным.

Теперь сам

Почему в квадрате со стороной d/2 не может быть двух точек ИЗ ОДНОЙ половины? И может ли там оказаться две точки из разных половин?