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