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

2014-01-25T03:38:16Z

188.162.64.33: /* Источники */

{{ptready}}
==Постановка задачи==
Дан ППЛГ и некая точка <tex>P</tex>. Нужно локализовать точку в ППЛГ (выяснить, над/под каким ребром ППЛГ расположена эта точка).

==Решение==
===Суть===
[[Файл:cgslabs.png|200px|thumb|right]]
Проведём через каждую вершину вертикальную прямую. Получим полосы (slabs). Пусть каждой полосе соответствует точка, через которую проведён левый край полосы. Будем хранить отсортированный массив <tex>x</tex>-координат, тогда за <tex>O(\log n)</tex> можно найти, в какой полосе лежит <tex>P</tex>.

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

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

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

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

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

==Время и память==
На запрос нужно <tex>O(\log n)</tex>, на препроцессинг — <tex>O(n \log n)</tex>; памяти нужно <tex>O(n)</tex>.

==Источники==
*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
*[http://wwwisg.cs.uni-magdeburg.de/ag/lehre/WS1213/GDS/slides/S12.pdf] Тут есть чуть подробнее про персистентные деревья

Викиконспекты - Вклад участника [ru]

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