264
правки
Изменения
м
→Существование триангуляции Делоне
}}
Воспользовавшись фактом выше, приходим к очевидному решение как за <tex>O(K)</tex> (где <tex> K </tex>- количество вершин в многоугольнике) триангулировать все многограники:берем любую точку в многогранике и соединяем её с остальными.
Так как в конечной триангуляции мы имеем <tex>O(N)</tex> треугольников, а каждый шаг мы добавляем 1 треугольник, то суммарно для всех многоугольник мы совершим не более <tex>O(N)</tex> операций.
