Участник:Muravyov — различия между версиями
Muravyov (обсуждение | вклад) |
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>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> | + | Доказательство ведётся индуктивно по <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:30, 27 апреля 2012
Триангуляция полигона — декомпозиция многоугольника
на множество треугольников, внутренние области которых попарно не пересекаются и объединение которых в совокупности составляет . В строгом смысле слова, эти треугольники могут иметь вершины только в вершинах исходного многоугольника.Простым многоугольником является односвязная фигура, стороны которой не пересекаются.
Теорема (О существовании триангуляции полигона): |
У любого простого -вершинного многоугольника существует триангуляция, причём количество треугольников в ней . |
Доказательство: |
Доказательство ведётся индуктивно по | . При теорема тривиальна. Рассмотрим случай при и предположим, что теорема выполняется при всех . Докажем существование диагонали в многоугольнике . Возьмём самую левую вершину многоугольника и две смежных с ней вершины и . Если отрезок принадлежит внутренней области — мы нашли диагональ. В противном случае, во внутренней области треугольника или на самом отрезке содержится одна или несколько вершин . Выберем самую наиболее далеко отстоящую от вершину . Отрезок, соединяющий и не может пересекать сторон , поскольку в противном случае одна из вершин это отрезка будет располагаться дальше от , чем . Это противоречит условию выбора . В итоге получаем, что — диагональ.