Изменения

Перейти к: навигация, поиск

Участник:Muravyov

Нет изменений в размере, 16:12, 5 мая 2012
Корректность
Допустим, что диагональ <tex>v_{i}v_{m}</tex> была построена с помощью ''HandleSplitVertex'' по достижению split вершины <tex>v_i</tex>. Рассмотрим четырёхугольник <tex>H</tex>, заключённый между <tex>e_j</tex> и <tex>e_k</tex> - левым и правым ребром относительно <tex>v_i</tex> и горизонтальными прямыми, проведёнными через <tex>v_i</tex> и <tex>v_m</tex>. Внутри <tex>H</tex>, не может находиться ни одной из вершин <tex>P</tex>, в противном случае <tex>helper(e_j)</tex> не равнялся бы <tex>v_m</tex>. Предположим теперь, что <tex>v_{i}v_{m}</tex> пересекает <tex>e_s</tex> одну из сторон <tex>P</tex>. Учитывая, что никаких вершин <tex>P</tex> не лежит внутри <tex>H</tex> и стороны <tex>P</tex> не пересекаются, то <tex>e_s</tex> должна пересечь либо отрезок, соединяющий <tex>e_j</tex> и <tex>v_m</tex>, либо <tex>e_j</tex> и <tex>v_i</tex>. Такое возможно только в случае, когда точками пересечения будут являться <tex>v_i</tex> или <tex>v_m</tex>, что не противоречит условию. Отсюда <tex>v_{i}v_{m}</tex> не пересекает ни одну из сторон <tex>P</tex> в посторонних точках.
Теперь рассмотрим случай с пересечением добавленной ранее диагональю. Поскольку внутри <tex>QH</tex> никаких вершин вершин находиться не может, и оба конца любой добавленной ранее диагонали должны лежать выше <tex>v_i</tex>, диагональ <tex>v_{i}v_m</tex> не может пересекать никакую из ранее добавленных диагоналей.
}}
184
правки

Навигация