1632
правки
Изменения
м
== См. также ==
* [[Алгоритм Бентли-Оттмана]]
rollbackEdits.php mass rollback
Нам потребуется две структуры данных.
Во-первых, мы будем хранить очередь событий <tex>Q</tex> в виде сбалансированного бинарного дерева поиска, что позволит извлекать следующее событие и вставлять новое событие в очередь за <tex>O(\log{m})</tex>, где <tex>m</tex> {{---}} количество элементов в очереди. Дерево будет отсортировано согласно порядку, введённому выше. Причём вместе с каждым событием мы будем хранить список отрезков, верхней точкой которых он является.
Во вторых, будем хранить статус <tex>T</tex> заметающей прямой: множество отрезков, пересекающих заметающую прямую в данный момент времени, упорядоченных слева направо. От статуса нам потребуется оптимальные вставка и удаление отрезков, поэтому по-прежнему удобно воспользоваться бинарным деревом поиска.
{{Лемма
|statement=Пусть <tex>p</tex> {{---}} точка пересечения нескольких отрезков, причем <tex>p</tex> не совпадает ни с одним из концов отрезков, участвующих в пересечении. Отсортируем отезки по углу вокруг <tex>p</tex> и пусть отрезки <tex>s_i</tex> и <tex>s_j</tex> окажутся соседними в сортировке. Тогда существует событие <tex>q</tex> с приоритетом выше, чем у <tex>p</tex>, такое что при обработке этого события <tex>s_i</tex> и <tex>s_j</tex> будут соседними в статусе.
||proof=Рассмотрим событие <tex>q</tex> которое будет обработано непосредственно перед <tex>p</tex>. Предположим, что при обработке этого события <tex>s_i</tex> и <tex>s_j</tex> не будут соседними в статусе. Это возможно только если между ними есть третий отрезок <tex>s</tex>. Но тогда или <tex>s</tex> пересекает какой-то из отрезков <tex>s_i, s_j</tex> в точке с приоритетом выше, чем у <tex>p</tex>, но ниже, чем у <tex>q</tex>; или <tex>s</tex> пересекает их оба в точке <tex>p</tex>, что противоречит тому, что они соседние в сортировке по углу; или конец отрезка имеет приоритет выше, чем <tex> p </tex>, но ниже, чем <tex> q </tex> и отрезок не пересекает <tex>s_i, s_j</tex>. Тогда в последнем случае нарушается тот факт, что <tex>q</tex> идет непосредственно перед <tex>p</tex>. Следовательно при обработке <tex>q</tex> <tex>s_i</tex> и <tex>s_j</tex> будут соседними в статусе.
}}
Очевидно, что статус в худшем случае занимает <tex>O(n)</tex> памяти, однако очередь событий может занимать <tex>O(n + I)</tex> памяти. Если модифицировать алгоритм так, что в очереди будут храниться только точки пересечения отрезков, соседних в статусе, то объём используемой памяти сократится до <tex>O(n)</tex>. Для этого нужно удалять точки пересечения отрезков, которые перестали быть соседними. Перед тем, как мы дойдём до точки удаленной точки, обязательно найдётся соседняя в статусе пара отрезков, которые пересекаются в этой точке, и она снова будет вставлена в очередь. Ясно, что такая оптимизация не влияет на время работы алгоритма.
== Источники ==
