Участник:Muravyov

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

Простым многоугольником является односвязная фигура, стороны которой не пересекаются.

Теорема (О существовании триангуляции полигона):

У любого простого [math]n[/math]-вершинного многоугольника [math]P[/math] существует триангуляция, причём количество треугольников в ней [math]n - 2[/math].

Доказательство:

[math]\triangleright[/math]

Доказательство ведётся индуктивно по [math]n[/math]. При [math]n = 3[/math] теорема тривиальна. Рассмотрим случай при [math]n \gt 3[/math] и предположим, что теорема выполняется при всех [math]m \lt n[/math]. Докажем существование диагонали в многоугольнике [math]P[/math].

[math]\triangleleft[/math]