Участник:Muravyov

Материал из Викиконспекты
Перейти к: навигация, поиск

Триангуляция полигона — декомпозиция внутренней области многоугольника [math]P[/math] на множество треугольников, внутренние области которых попарно не пересекаются и объединение которых в совокупности составляет [math]P[/math]. В строгом смысле слова, эти треугольники могут иметь вершины только в вершинах исходного многоугольника. Кроме того, случаи триангуляции простого многоугольника и многоугольника с полигональными отверстиями рассматриваются отдельно.

Теорема (О существовании триангуляции полигона):
У любого простого [math]n[/math]-вершинного многоугольника существует триангуляция, причём количество треугольников в ней [math]n - 2[/math].
Доказательство:
[math]\triangleright[/math]
Схема доказательства — такая же, как и с формулой меры подграфика функции — от простого к сложному.
[math]\triangleleft[/math]