Локализация в ППЛГ методом полос (персистентные деревья)

Конспект написан не до конца, но основные вещи уже есть.

Постановка задачи

Дан ППЛГ и некая точка [math]P[/math]. Нужно локализовать точку в ППЛГ (выяснить, над/под каким ребром ППЛГ расположена эта точка).

Решение

Суть

Проведём через каждую вершину вертикальную прямую. Получим полосы (slabs). Пусть каждой полосе соответствует точка, через которую проведён левый край полосы. Будем хранить отсортированный массив [math]x[/math]-координат, тогда за [math]O(\log n)[/math] можно найти, в какой полосе лежит [math]P[/math].

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

Персистентные деревья

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

Один из способов сделать дерево частично персистентным — node-copying (или path-copying, в разных источниках по-разному). Храним массив корней дерева. Когда нам нужно изменить ноду, мы создаём в этом массиве новый корень, но его поля left и right совпадают с таковыми в предыдущем корне. Далее мы идём от корня к ноде, которую хотим изменить. Все вершины по пути мы «копируем» так же, как и корень, при этом у предка меняем соответствующий указатель на новый. После этого мы меняем нужную нам ноду. Таким образом, для такого дерева нам нужно [math]O(n \log n)[/math] памяти.

Можно усовершенствовать этот способ. Теперь в каждой ноде будет храниться номер версии и поля для ленивого изменения дерева: фиксированное количество запасных указателей left и right и номера версий для них. Когда мы хотим изменить ноду, вместо копирования записываем изменения в запасные указатели, если они ещё есть, иначе создаём новую ноду и соответственно исправляем её предка. Для поиска по версиям используем бинпоиск. Этот способ называется limited node copying, для него нужно O(n) памяти, потому что амортизированно за один апдейт копируем O(1) нод.

Локализация в полосе

Воспользуемся сбалансированным частично персистентным деревом для хранения отрезков в полосах. Каждая полоса — это новая версия дерева.

Время и память

На запрос нужно [math]O(\log n)[/math], на препроцессинг — [math]O(n \log n)[/math]; памяти нужно [math]O(n)[/math].

Источники

• Goodman, O'Rourke "Handbook of Discrete and Computational Geometry", 2004 г., стр. 775-776
• Sarnak, Tarjan "Planar Point Location Using Persistent Search Trees"
• de Berg и компания, Computational Geometry, третье издание, стр. 122-123
• [1] Тут есть чуть подробнее про персистентные деревья