Участник:Muravyov

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

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

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

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

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

[math]\triangleright[/math]

Доказательство ведётся по индукции.

[math]\triangleleft[/math]