Изменения

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

Участник:Muravyov

432 байта добавлено, 14:11, 4 мая 2012
Корректность
Остаётся доказать, что диагонали, построенные в процессе выполнения алгоритма, не попарно не пересекаются и не пересекают стороны <tex>P</tex>.
Рассмотрим случай выполнения функции ''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>H</tex>, не может находиться ни одной из вершин <tex>P</tex>, в противном случае <tex>helper(e_j)</tex> не равнялся бы <tex>v_m</tex>.
}}
184
правки

Навигация