184
правки
Изменения
→Корректность
===== Корректность =====
{{Лемма
|statement=
Функция ''MakeMonotone(P)'' корректно выполняет разбиение многоугольника <tex>P</tex>. Другими словами эта функция добавляет в <tex>P</tex> множество не пересекающихся диагоналей, которые разбивают <tex>P</tex> на монотонные части.
|proof=
Тот факт, что <tex>P</tex> разбивается на монотонные части следует из предыдущей леммы.
Остаётся доказать, что диагонали, построенные в процессе выполнения алгоритма, не попарно не пересекаются и не пересекают стороны <tex>P</tex>.
Рассмотрим случай выполнения функции ''HandleSplitVertex'', поскольку это наиболее общий случай: split вершина может быть соединена со всеми типами вершин, в отличие от остальных функций. В них рассматриваемая в данный момент вершина может быть соединена только с merge вершиной. Допустим, что диагональ <tex>v_{i}v_{m}</tex> была построена с помощью ''HandleSplitVertex'' по достижению split вершины <tex>v_i</tex>.
}}
===== Оценкка работы =====
