Участник:Muravyov — различия между версиями
Muravyov (обсуждение | вклад) |
Muravyov (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
'''Триангуляция полигона ''' — декомпозиция внутренней области многоугольника <tex>P</tex> на множество треугольников, внутренние области которых попарно не пересекаются и объединение которых в совокупности составляет <tex>P</tex>. В строгом смысле слова, эти треугольники могут иметь вершины только в вершинах исходного многоугольника. | '''Триангуляция полигона ''' — декомпозиция внутренней области многоугольника <tex>P</tex> на множество треугольников, внутренние области которых попарно не пересекаются и объединение которых в совокупности составляет <tex>P</tex>. В строгом смысле слова, эти треугольники могут иметь вершины только в вершинах исходного многоугольника. | ||
| − | + | Простым многоугольником является односвязная фигура, стороны которой не пересекаются. | |
{{Теорема | {{Теорема | ||
|about = О существовании триангуляции полигона | |about = О существовании триангуляции полигона | ||
|statement = | |statement = | ||
| − | У любого простого <tex>n</tex>-вершинного многоугольника существует триангуляция, причём количество треугольников в ней <tex>n - 2</tex>. | + | У любого простого <tex>n</tex>-вершинного многоугольника <tex>P</tex> существует триангуляция, причём количество треугольников в ней <tex>n - 2</tex>. |
|proof= | |proof= | ||
| − | Доказательство ведётся по | + | Доказательство ведётся индуктивно по <tex>n</tex>. При <tex>n = 3</tex> теорема тривиальна. Рассмотрим случай при <tex>n > 3</tex> и предположим, что теорема выполняется при всех <tex>m < n</tex>. Докажем существование диагонали в многоугольнике <tex>P</tex>. |
}} | }} | ||
Версия 19:56, 26 апреля 2012
Триангуляция полигона — декомпозиция внутренней области многоугольника на множество треугольников, внутренние области которых попарно не пересекаются и объединение которых в совокупности составляет . В строгом смысле слова, эти треугольники могут иметь вершины только в вершинах исходного многоугольника.
Простым многоугольником является односвязная фигура, стороны которой не пересекаются.
| Теорема (О существовании триангуляции полигона): |
У любого простого -вершинного многоугольника существует триангуляция, причём количество треугольников в ней . |
| Доказательство: |
| Доказательство ведётся индуктивно по . При теорема тривиальна. Рассмотрим случай при и предположим, что теорема выполняется при всех . Докажем существование диагонали в многоугольнике . |
