184
правки
Изменения
→Корректность
Рассмотрим случай выполнения функции ''HandleSplitVertex'', поскольку это наиболее общий случай: split вершина может быть соединена со всеми типами вершин, в отличие от остальных функций. В них рассматриваемая в данный момент вершина может быть соединена только с merge вершиной.
Допустим, что диагональ <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>
}}
