Участник: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]v[/math] многоугольника [math]P[/math] и две смежных с ней вершины [math]u[/math] и [math]w[/math]. Если отрезок [math]uw[/math] принадлежит внутренней области [math]P[/math] — мы нашли диагональ. В противном случае, во внутренней области треугольника [math]uwv[/math] или на самом отрезке [math]uw[/math] содержится одна или несколько вершин [math]P[/math].

[math]\triangleleft[/math]