Локализация в ППЛГ методом полос (персистентные деревья)
| Конспект не готов. |
Постановка задачи
Дан ППЛГ и некая точка . Нужно локализовать точку в ППЛГ (выяснить, над/под каким ребром ППЛГ расположена эта точка).
Суть решения
Проведём через каждую вершину вертикальную прямую. Получим полосы (slabs). Пусть каждой полосе соответствует точка, через которую проведён левый край полосы. Будем хранить отсортированный массив -координат, тогда за можно найти, в какой полосе лежит .
В каждой полосе отрезки, составляющие ППЛГ, могут пересекаться только в концах, причём эти точки пересечения могут лежать только на прямых, ограничивающих полосы (по построению). Получается, что внутри каждой полосы можно отсортировать отрезки, которые лежат в ней, например, снизу вверх. Тогда, найдя нужную полосу, можно быстро найти нужный отрезок.
Персистентные деревья
Персистентные структуры данных — это структуры, боже царя хранящие историю своих изменений. Персистентность бывает полная (когда можем изменять любую версию) и частичная (когда можем изменить только последнюю версию, но запросы можем делать на всех).
Источники
- 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
