418
правок
Изменения
Новая страница: «{{notready}} ==Постановка задачи== Дан ППЛГ и некая точка <tex>P</tex>. Нужно локализовать точку в ППЛ...»
{{notready}}
==Постановка задачи==
Дан ППЛГ и некая точка <tex>P</tex>. Нужно локализовать точку в ППЛГ (выяснить, над/под каким ребром ППЛГ расположена эта точка).
==Суть решения==
Проведём через каждую вершину вертикальную прямую. Получим полосы (slabs). Пусть каждой полосе соответствует точка, через которую проведён левый край полосы. Будем хранить отсортированный массив <tex>x</tex>-координат, тогда за <tex>O(\log n)</tex> можно найти, в какой полосе лежит <tex>P</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
==Постановка задачи==
Дан ППЛГ и некая точка <tex>P</tex>. Нужно локализовать точку в ППЛГ (выяснить, над/под каким ребром ППЛГ расположена эта точка).
==Суть решения==
Проведём через каждую вершину вертикальную прямую. Получим полосы (slabs). Пусть каждой полосе соответствует точка, через которую проведён левый край полосы. Будем хранить отсортированный массив <tex>x</tex>-координат, тогда за <tex>O(\log n)</tex> можно найти, в какой полосе лежит <tex>P</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
