Изменения

== Теорема о существовании трингуляции. ==

{{Теорема

|about = О существовании триангуляции многоугольника

Докажем, что триангуляция <tex>P</tex> состоит из <tex>n - 2</tex> треугольников. Рассмотрим произвольную диагональ <tex>d</tex> в триангуляции <tex>T_P</tex>. <tex>d</tex> делит <tex>P</tex> на два многоугольника <tex>P_1</tex> и <tex>P_2</tex>, количество вершин в которых <tex>m_1</tex> и <tex>m_2</tex> соответственно. Каждая вершина <tex>P</tex> встречается только в одном из двух многоугольников <tex>P_1</tex> и <tex>P_2</tex>, за исключением тех, которые являются концами <tex>d</tex>, поэтому справедливо следующее: <tex>m_1 + m_2 = n + 2</tex>. По индукции, любая триангуляция <tex>P_i</tex> состоит из <tex>m_i - 2</tex> треугольников, откуда следует, что <tex>T_P</tex>. состоит из <tex>(m_1 - 2) + (m_2 - 2) = n - 2</tex> треугольников.

}}

== Способы выполнения триангуляции ==

Выпуклый многоугольник является тривиальным случаем, триангуляция осуществляется за линейное время добавлением диагоналей от одной вершины ко всем другим вершинам. В том числе есть и другие методы, общее число способов триангуляции выпуклого <tex>n</tex>-угольника непересекающимися диагоналями является: <tex> \frac {4\cdot 6 \cdot 10 \cdot... \cdot(4n - 10)} {(n - 1)!}</tex>