Триангуляция многоугольника

Мы рассмотрим частный вид многоугольников на клетчатой бумаге, которому в формуле Пика соответствуют значения . Но от этого частного случая можно перейти сразу к самому общему, воспользовавшись теоремой о разрезании на треугольники произвольного многоугольника (клетчатая бумага больше не нужна).

Пусть на плоскости задан некоторый многоугольник и некоторое конечное множество К точек, лежащих внутри многоугольника и на его границе (причём все вершины многоугольника принадлежат множеству К).

Триангуляцией с вершинами К называется разбиение данного многоугольника на треугольники с вершинами в множестве К такое, что каждая точка из К служит вершиной каждому из тех треугольников триангуляции, которым эта точка принадлежит (то есть точки из К не попадают внутрь или на стороны треугольников, рис. 1.37).

Рис. 1.37

Теорема 2. а) Любой n -угольник можно разрезать диагоналями на треугольники, причём количество треугольников будет равно n – 2 (это разбиение – триангуляция с вершинами в вершинах n -угольника).

б) Пусть на границе многоугольника отмечено r точек (включая все вершины), внутри – ещё i точек. Тогда существует триангуляция с вершинами в отмеченных точках, причём количество треугольников такой триангуляции будет равно .

Разумеется, а) – частный случай б), когда .

Справедливость этой теоремы следует из следующих утверждений.

1) Из вершины наибольшего угла n -угольника () всегда можно провести диагональ, целиком лежащую внутри многоугольника.

2) Если n -угольник разрезан диагональю на р -угольник и q -угольник, то .

3) Сумма углов n -угольника равна .

4) Любой n -угольник можно разрезать диагоналями на треугольника.

5) Для любого треугольника, внутри и на границе которого отмечены несколько точек (в том числе и все три его вершины), существует триангуляция с вершинами в отмеченных точках.

6) То же самое верно и для любого n -угольника.

7) Число треугольников триангуляции равно , где i и r – количество отмечены несколько точек соответственно внутри и на границе многоугольника. Назовём разбиение n -угольника на несколько многоугольников правильным, если каждая вершина одного из многоугольников разбиения служит вершиной всех других многоугольников разбиения, которым она принадлежит. 8) Если из вершин k -угольников, на которые разбит правильным образом n -угольник, i вершин лежат внутри и r – на границе n -угольника, то количество k -угольников равно