Изменения

Доказательство ведётся индуктивно по <tex>n</tex>. При <tex>n = 3</tex> теорема тривиальна. Рассмотрим случай при <tex>n > 3</tex> и предположим, что теорема выполняется при всех <tex>m < n</tex>. Докажем существование диагонали в многоугольнике <tex>P</tex>. Возьмём самую левую по оси <tex>x</tex> вершину <tex>v</tex> многоугольника <tex>P</tex> и две смежных с ней вершины <tex>u</tex> и <tex>w</tex>. Если отрезок <tex>uw</tex> принадлежит внутренней области <tex>P</tex> — мы нашли диагональ. В противном случае, во внутренней области треугольника <tex>\Delta uwv</tex> или на самом отрезке <tex>uw</tex> содержится одна или несколько вершин <tex>P</tex>. Выберем самую из них наиболее далеко отстоящую удалённую от <tex>uw</tex> вершину <tex>v'</tex>. Отрезок, соединяющий <tex>v</tex> и <tex>v'</tex> не может пересекать сторон ребро <tex>P</tex>, поскольку в противном случае одна из вершин это отрезка этого ребра будет располагаться дальше от <tex>uw</tex>, чем <tex>v'</tex>. Это противоречит условию выбора <tex>v'</tex>. В итоге получаем, что <tex>v'v</tex> — диагональ.

Обозначим за <tex>\phi</tex> внутренний угол при некоторой вершине вершине и определим далее пять типов вершин, четыре из которых являются поворотными:

Предположим, что <tex>P</tex> не <tex>y</tex>-монотонный. Тогда докажем, что <tex>P</tex> содержит split и merge вершины. Поскольку <tex>P</tex> не <tex>y</tex>-монотонный, существует горизонтальная прямая <tex>l</tex> , которая пересекает его стороны более двух раз. Выберем <tex>l</tex> таким образом, чтобы самой левой компонентой пересечения <tex>l</tex> и <tex>P</tex> был бы отрезок <tex>pq</tex>. Далее будем двигаться наверх по сторонам <tex>P</tex>, начиная от точки <tex>q</tex>. В результате в некоторой точке <tex>r</tex>, где <tex>r \neq p</tex> (случай '''(a)''' на рисунке), прямая <tex>l</tex> снова пересечёт одну из сторон <tex>P</tex>. Отсюда самая высокая точка, которую мы достигли во время движения по сторонам <tex>P</tex>, будет split вершиной.

Если же <tex>r = p</tex> (случай '''(b)''' на рисунке), начём опять двигаться по сторонам <tex>P</tex> теперь уже вниз. Как и в предыдущем случае найдётся некоторая точка <tex>r'</tex>, которая будет результатом пересечения <tex>l</tex> и <tex>P</tex>. При этом <tex>r' \neq p</tex>, в противном случае <tex>l</tex> будет пересекать <tex>P</tex> только два раза, то есть что противоречит выбору <tex>Pl</tex> будет <tex>y</tex>-монотонным, что противоречит нашему предположению. Аналогично предыдущему случаю, выберем теперь самую низкую точку, которую мы достигли во время движения по сторонам P. Она будет merge вершиной.

# '''''Split вершина'''''. Пусть <tex>e_j</tex> и <tex>e_k</tex> — ближайшее левое и правое ребро относительно split вершины <tex>v_i</tex>, которые <tex>l</tex> пересекает в данный момент. Нам нужно найти вершину, лежащую между <tex>e_j</tex> и <tex>e_k</tex>, наиболее приближённую к <tex>l</tex>, либо если такой точки не существет выбрать минимальную из верхних вершин <tex>e_j</tex> и <tex>e_k</tex>. Для этого будем хранить указатель на искомую вершину у левого ребра <tex>e_j</tex>, который можно заранее вычислить. Тип вершины, хранящийся в <tex>helper</tex> не имеет значения. Таким образом, чтобы построить диагональ для split вершины нужно обратиться к указателю <tex>helper(e_j)</tex> её левого ребра, которое <tex>l</tex> пересекает в данный момент.# '''''Merge вершина'''''. В отличие от случая со split вершиной заранее вычислить указатель <tex>helper</tex> нельзя, поскольку merge вершина <tex>v_i</tex> должна быть соединена с вершиной, лежащей ниже заметающей прямой <tex>l</tex>. Для этого в <tex>helper(e_j)</tex> - левого относительно <tex>v_i</tex> ребра запишем саму <tex>v_i</tex>. Далее спускаем заметающую прямую вниз к следующей вершине <tex>v_m</tex>, обращаемся к <tex>helper</tex>'у её левого ребра. Проверяем, если там хранится merge вершина, строим диагональ <tex>v_{i}v_{m}</tex>. Последняя проверка осуществляется для любого типа вершины, кроме split, согласно п.1.[[Файл:Merge_case_1_2.jpg|500px|thumb|center|Обработка ''megremerge'' вершины <tex>v_i</tex>. На рисунке слева <tex>v_i</tex> записывается в качестве <tex>helper</tex>'а своего левого ребра. На правом рисунке ближайшая вершина <tex>v_m</tex> при обращении к своему левому ребру <tex>helper(e_j)</tex> находит <tex>v_i</tex> и образует диагональ <tex>v_{i}v_m</tex>]]

Изначально в многоугольнике содержится <tex>\mathcal{O}(n)</tex> ушей. Нетрудно понять, что в процессе отрезания ушей, смежные точки могут тоже становиться ушами. В результате триангуляции образуется <tex>n - 3</tex> диагонали, соответственно максимальное количество вершин, которые в процессе могут становиться ушами <tex>2n - 6</tex>. Итого общее количество ушей будет <tex>\mathcal{O}(n)</tex>. Определить, является ли вершина ухом можно за <tex>\mathcal{O}(n)</tex>, поскольку используется алгоритм определения принадлежности точки треугольнику — это <tex>\mathcal{O}(31)</tex>. Таким образом общий процесс отрезания ушей займёт <tex>\mathcal{O}(n^2)</tex>. Невыпуклых вершин всего <tex>\mathcal{O}(n)</tex>, каждая из них обрабатывается за константу, поэтому общее время для их обработки <tex>\mathcal{O}(n)</tex>. Списки рёбер и вершин строятся за линейное время, добавление ребра и удаление вершины в каждом из них работает за константу. Общее время <tex>\mathcal{O}(n^2)</tex>. Поскольку храним только два списка — память линейная.