74
правки
Изменения
м
→Доказательство корректности
{{Лемма
|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> будут соседними в статусе.
}}
