Изменения

Будем рассматривать вершины многоугольника в порядке обхода. Индексирование вершин для удобства будем вести по модулю <tex>n</tex>, т.е. <tex>v_{-1} = v_{n-1}</tex> и <tex>v_0 = v_n</tex>. Если вершина <tex>v_i</tex> является ухом, построим диагональ <tex>v_{i+1}v_{i-1}</tex> и отрежем треугольник <tex>\Delta v_{i-1}v_{i}v_{i+1}</tex> от <tex>P</tex>. В противном случае переходим к следующей вершине <tex>v_{i+1}</tex> в порядке обхода.

При проверке каждой вершину следует для начала проверить, является ли она выпуклой, в противном случае её просто нет надобности рассматривать в качестве уха. Это несложно сделать, воспользовавшись [[Предикат_"левый_поворот"|левым поворотом]]. "Ушную" проверку вершины будем осуществлять алгоритмом принадлежности точки <tex>n</tex>-угольнику (в нашем случае треугольнику). В качестве поддерживаемых структур удобно хранить два DCEL, в одном из которых отрезать уши, а в другом строить новые диагонали.

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