Конспект: поиск по диапазону, квадродеревья и BSP

Понятия

Поиск по диапазону - назвать или посчитать точки в прямоугольнике.

Ячейка узла kd-дерева - прямоугольник, где лежат точки его поддерева.

Дерево диапазонов - дерево по x, в каждом узле точки поддерева по y. Канонические узлы - узлы, на которые раскладывается отрезок номеров. Частичное каскадирование - ссылки из списка родителя в списки детей вместо повторных поисков.

Квадродерево - деление квадрата на четыре, пока в нём больше одной точки. Кривая Мортона - ключ из чередующихся битов x и y.

BSP-дерево - разбиение плоскости прямыми отрезков сцены. Алгоритм художника - рисование сзади вперёд.

Что унести

ОДНОМЕРНО                 два двоичных поиска, O(log n + k)
5000 цен: 24-25 шагов при любом ответе

kd-ДЕРЕВО: ПРЯМОУГОЛЬНИК             O(√n + k)
в d измерениях                       O(n^(1 − 1/d) + k)
в поддерево - если прямоугольник задевает ячейку,
ячейка внутри - выдать целиком
Q(n) = 2 + 2Q(n/4) = O(√n): сторона пересекает √n ячеек
1024 точки: квадрат 38 узлов, полосы 62 и 93, весь квадрат 1024

ДЕРЕВО ДИАПАЗОНОВ                    O(log² n + k)
с частичным каскадированием          O(log n + k)
построение слиянием O(n log n), память n (log n + 1)
запрос: номера по x → канонические узлы → поиск по y в каждом
1024 точки: память 11 264, полосы 22 и 41 шаг
128 / 512 / 2048: шагов 33 / 51 / 71 - как log² n
отрезок номеров: [первый x >= x1, первый x > x2), пары (x, y)

СЕТКА И КВАДРОДЕРЕВО
сетка: корзина (x · m // S, y · m // S); хороша при равномерной плотности
    скопление: окно нашло 412, проверило 3600
квадродерево: глубина <= log₂(S / c) + 1,5, c - ближайшая пара
    64 точки - глубина 7; +пара на расстоянии 1 в поле 2¹⁶ - 16
Мортон: чередовать биты; квадрат дерева = отрезок ключей
геохеши, тайлы карт, H3 (12 пятиугольников на уровне)

BSP И ХУДОЖНИК
авторазбиение: прямая отрезка, пересечённые - разрезать
кусок = исходный отрезок + интервал параметра (точно в целых)
обход: дальняя половина → отрезки узла → ближняя
непересекающиеся отрезки в 2D:
    случайный порядок: <= n + 2n · ln n кусков в ожидании
    худший вход: Θ(n log n / log log n) (Тот)
3D: размер может достигать n²
30 стен: BSP 0 ошибок, сортировка по середине 15

Ловушки джокера

Проверять каждую точку ячейки, лежащей внутри запроса. Выдача та же, а большие запросы стоят n.

Два одномерных индекса вместо двумерного. Пересечение списков стоит сумму их длин.

Граница x2 без +1. Точки ровно на правой границе выпадают.

Сетка на скоплениях. Одна корзина держит всех.

Квадродерево на дубликатах. Деление не кончается без предела глубины.

Сортировка по расстоянию вместо BSP. Длинные стены заслоняют «более близкие» по середине.

Куски BSP во float. Конец куска уезжает на чужую сторону прямой.

Проверь себя

Откуда √n в прямоугольном запросе kd-дерева? Как дерево диапазонов избавляется от корня и чем за это платит? Что даёт частичное каскадирование? Когда сетка лучше дерева и от чего зависит глубина квадродерева? Почему обход BSP даёт порядок художника для любой точки зрения и сколько кусков при случайном порядке разрезов?

• Приоритетное дерево поиска: min-куча по x и медианное разбиение по y; трёхсторонний запрос (-∞,x]×[y₁,y₂] стоит O(log n+k), память O(n). Четырёхсторонний запрос этой гарантии не наследует.

• Симплексный запрос в 2D - треугольник. Симплициальное разбиение контролирует число пересечений прямой с группами; конструкция de Berg даёт O(n^(1/2+ε)) в O(n) памяти, выдача добавляет k.