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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 8: Строка 8:
  
 
|proof=
 
|proof=
Доказательство ведётся индуктивно по <tex>n</tex>. При <tex>n = 3</tex> теорема тривиальна. Рассмотрим случай при <tex>n > 3</tex> и предположим, что теорема выполняется при всех <tex>m < n</tex>. Докажем существование диагонали в многоугольнике <tex>P</tex>. Возьмём самую левую вершину <tex>v</tex> многоугольника <tex>P</tex> и две смежных с ней вершины <tex>u</tex> и <tex>w</tex>. Если отрезок  <tex>uw</tex> принадлежит внутренней области <tex>P</tex> — мы нашли диагональ. В противном случае, во внутренней области треугольника <tex>uwv</tex> или на самом отрезке <tex>uw</tex> содержится одна или несколько вершин <tex>P</tex>.
+
Доказательство ведётся индуктивно по <tex>n</tex>. При <tex>n = 3</tex> теорема тривиальна. Рассмотрим случай при <tex>n > 3</tex> и предположим, что теорема выполняется при всех <tex>m < n</tex>. Докажем существование диагонали в многоугольнике <tex>P</tex>. Возьмём самую левую вершину <tex>v</tex> многоугольника <tex>P</tex> и две смежных с ней вершины <tex>u</tex> и <tex>w</tex>. Если отрезок  <tex>uw</tex> принадлежит внутренней области <tex>P</tex> — мы нашли диагональ. В противном случае, во внутренней области треугольника <tex>uwv</tex> или на самом отрезке <tex>uw</tex> содержится одна или несколько вершин <tex>P</tex>. Выберем самую наиболее далеко отстоящую от <tex>uw</tex> вершину <tex>v'</tex>. Отрезок, соединяющий <tex>v</tex> и <tex>v'</tex> не может пересекать сторон <tex>P</tex>, поскольку в противном случае одна из вершин это отрезка будет располагаться дальше от <tex>uw</tex>, чем <tex>v'</tex>. Это противоречит условию выбора <tex>v'</tex>. В итоге получаем, что <tex>v'v</tex> - диагональ.  
  
  
 
}}
 
}}

Версия 10:29, 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]\triangleleft[/math]