264
правки
Изменения
м
→Существование триангуляции Делоне
{{Лемма
|about=1
|statement= Сечение сферы плоскостью есть круг, а основание перпендикуляра , проведенного из центра шара к пересекаемой плоскости , есть центр круга, полученного в сечении.
|proof=
[[Файл:drawing.png|400px|thumb|right|]]
Поскольку никакие четыре точки не лежат на одной окружности в исходном наборе точек, а значит, гранями выпуклой оболочки будут треугольнички.
Значит, триангуляция существует.
А поскольку выпуклая оболочка единственна, можно сказать,что и триангуляция единственна.
}}
}}
Воспользовавшись фактом выше, приходим к очевидному решение решению как за <tex>O(K)</tex> (где <tex> K </tex>- количество вершин в многоугольнике) триангулировать все многограники:берем любую точку в многогранике и соединяем её с остальными.
Так как в конечной триангуляции мы имеем <tex>O(N)</tex> треугольников, а каждый шаг мы добавляем 1 треугольник, то суммарно для всех многоугольник мы совершим не более <tex>O(N)</tex> операций.
