Участник:Muravyov — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 11: Строка 11:
 
Любая диагональ делит <tex>P</tex> на два многоугольника <tex>P_1</tex> и <tex>P_2</tex>. За <tex>m_1</tex> и <tex>m_2</tex> обозначим количество вершин в <tex>P_1</tex> и <tex>P_2</tex> соответственно. <tex>m_1 < n</tex> и <tex>m_2 < n</tex>, поэтому по предположению индукции у <tex>P_1</tex> и <tex>P_2</tex> существует триангуляция, следовательно и у <tex>P</tex> она существует.
 
Любая диагональ делит <tex>P</tex> на два многоугольника <tex>P_1</tex> и <tex>P_2</tex>. За <tex>m_1</tex> и <tex>m_2</tex> обозначим количество вершин в <tex>P_1</tex> и <tex>P_2</tex> соответственно. <tex>m_1 < n</tex> и <tex>m_2 < n</tex>, поэтому по предположению индукции у <tex>P_1</tex> и <tex>P_2</tex> существует триангуляция, следовательно и у <tex>P</tex> она существует.
  
Докажем, что триангуляция <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</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> треугольников.
 
}}
 
}}

Версия 10:56, 27 апреля 2012

Триангуляция полигона — декомпозиция многоугольника [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]uw[/math] вершину [math]v'[/math]. Отрезок, соединяющий [math]v[/math] и [math]v'[/math] не может пересекать сторон [math]P[/math], поскольку в противном случае одна из вершин это отрезка будет располагаться дальше от [math]uw[/math], чем [math]v'[/math]. Это противоречит условию выбора [math]v'[/math]. В итоге получаем, что [math]v'v[/math] — диагональ. Любая диагональ делит [math]P[/math] на два многоугольника [math]P_1[/math] и [math]P_2[/math]. За [math]m_1[/math] и [math]m_2[/math] обозначим количество вершин в [math]P_1[/math] и [math]P_2[/math] соответственно. [math]m_1 \lt n[/math] и [math]m_2 \lt n[/math], поэтому по предположению индукции у [math]P_1[/math] и [math]P_2[/math] существует триангуляция, следовательно и у [math]P[/math] она существует.

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