Изменения

Изначально в многоугольнике содержится <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>. Поскольку храним только два списка — память линейная.