Изменения

В общем случае в произвольном <tex>n</tex>-угольнике всего <tex>n^2</tex> возможных вариантов построения диагоналей. За <tex>\mathcal{O}(n)</tex> проверим каждый из них. Для этого выясним:

* пересекает ли данная диагональ многоугольник — находится за линейное время проверкой по всем рёбрам

Чтобы построить триангуляцию нужно найти <tex>n - 3</tex> диагоналей. В результате получается оценка <tex>\mathcal{O}(n^4)</tex>.