Пусть дан n угольник у него m невыпуклых углов и мы знаем последовательность их расположения. Надо минимизировать
кол-во треугольников на которые его можно разрезать. Я пришел к выводу, что как минимум там будет (n - 2 - m) треугольников. Но всегда ли этот многоугольник так разрезаем или может есть более строгое условие?
Я постарался понятно объяснить.
-- 23.09.2016, 14:29 --Вершинная триангуляция

-угольника содержит ровно

треугольников. Это классический результат, связанный с формулой о сумме внутренних углов многоугольника (

). Если в триангуляцию вы добавите новые вершины на сторонах и внутри многоугольника, то

только увеличится. Количество не выпуклых углов на результат не влияет.
Обновление: при подсчёте треугольников я не принимал во внимание многоугольники у которых все вершины кроме трёх вырожденные. Если разрешить такие треугольники, то можно сделать

. Например шестиугольник можно разрезать на три треугольника.
Так что "классические" оценки верны только если никакие три точки не лежат на одной прямой.
Это оценки для выпуклых многоугольников
-- 23.09.2016, 14:34 --
6-угольник с последовательностью углов ВВВНВН можно разрезать на 2 треугольника.
В - выпуклый
Н - невыпуклый
-- 23.09.2016, 14:34 --Тут оценка
![$\[K = N - 2\]$ $\[K = N - 2\]$](https://dxdy-02.korotkov.co.uk/f/9/8/6/9864ec7e26027a76ae3afc6bb0ece1fd82.png)
не работает.