184
правки
Изменения
Нет описания правки
=== Примитивный алгоритм ===
В произвольном <tex>n</tex>-угольнике всего <tex>n^2</tex> возможных вариантов построения диагоналей. За <tex>\mathcal{O}(n)</tex> проверим каждый из них. Для этого выясним:
* пересекает ли данная диагональ многоугольник - — находится за линейное время проверкой по всем рёбрам
* принадлежит ли диагональ внутренней область многоугольника.
Чтобы построить триангуляцию нужно найти <tex>n - 3</tex> диагоналей. В результате получается оценка <tex>\mathcal{O}(n^4)</tex>.
