Разрезание на треугольники

[sa233091]

Недавно задумался над такой задачей: пусть мы имеем $\[n\]$-угольник. Сколько он должен иметь выпуклых и невыпуклых углов и в какой последовательности они должны распологаться, чтоб этот многоугольник можно было разрезать на
$\[k\]$ треугольников?

-- 23.09.2016, 11:40 --

Пришел к выводу, что если мы имеем n угольник и там m невыпуклых углов.
То его можно разрезать не менее чем на (n - 2 - m) треугольников. Но всегда ли так можно разрезать? И есть ли лучшая оценка?

[gris]

Как-то не очень хорошо звучит в Вашем случае: улучшить оценку типа "не менее". Вроде бы она улучшается путём отодвигания левой границы вправо, но в любом разрезании количество треугольников всегда можно запросто увеличить на один. А цель состоит в отодвигании левой границы влево

[sa233091]

gris в сообщении #1153857 писал(а):

Как-то не очень хорошо звучит в Вашем случае: улучшить оценку типа "не менее". Вроде бы она улучшается путём отодвигания левой границы вправо, но в любом разрезании количество треугольников всегда можно запросто увеличить на один. А цель состоит в отодвигании левой границы влево

Почему влево? Ну я просто говорю, что меньше (n - 2 - m) не получится. А может быть (n - 2 - m) тоже не получится, может есть оценка более строгая?

[gris]

У меня просто брюзжание по поводу слов оценка, улучшение, более строгая.
Ну вот возьмём случай $(5,1)$. По Вашей формуле $k=2$. А что такое $k$?
Я могу трактовать так:
Существует пятиугольник ровно с одним невыпуклым углом, который можно разрезать на два треугольника. Да.
Любой пятиугольник ровно с одним невыпуклым углом можно разрезать на два треугольника. Нет.
Что именно Вы имели в виду в задаче, непонятно, хотя догадываться можно. Но по разному.

[slavav]

Вершинная триангуляция $N$-угольника содержит ровно $K = N - 2$ треугольников. Это классический результат, связанный с формулой о сумме внутренних углов многоугольника ($\pi(N - 2)$). Если в триангуляцию вы добавите новые вершины на сторонах и внутри многоугольника, то $K$ только увеличится. Количество не выпуклых углов на результат не влияет.

Обновление: при подсчёте треугольников я не принимал во внимание многоугольники у которых все вершины кроме трёх вырожденные. Если разрешить такие треугольники, то можно сделать $K < N - 2$. Например шестиугольник можно разрезать на три треугольника.
Так что "классические" оценки верны только если никакие три точки не лежат на одной прямой.

[arseniiv]

Я так и не понял, что за невыпуклые и выпуклые углы такие.

[gris]

Невыпуклый больше развёрнутого, но меньше полного.

[slavav]

Выпуклый угол - внутренний угол многоугольника $(0, \pi]$, невыпуклый - $(\pi, 2\pi)$. От терминология из вычислительной геометрии.

[sa233091]

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

-- 23.09.2016, 14:29 --

slavav в сообщении #1153908 писал(а):

Вершинная триангуляция $N$-угольника содержит ровно $K = N - 2$ треугольников. Это классический результат, связанный с формулой о сумме внутренних углов многоугольника ($\pi(N - 2)$). Если в триангуляцию вы добавите новые вершины на сторонах и внутри многоугольника, то $K$ только увеличится. Количество не выпуклых углов на результат не влияет.

Обновление: при подсчёте треугольников я не принимал во внимание многоугольники у которых все вершины кроме трёх вырожденные. Если разрешить такие треугольники, то можно сделать $K < N - 2$. Например шестиугольник можно разрезать на три треугольника.
Так что "классические" оценки верны только если никакие три точки не лежат на одной прямой.

Это оценки для выпуклых многоугольников

-- 23.09.2016, 14:34 --


6-угольник с последовательностью углов ВВВНВН можно разрезать на 2 треугольника.
В - выпуклый
Н - невыпуклый

-- 23.09.2016, 14:34 --

Тут оценка $\[K = N - 2\]$ не работает.

[slavav]

sa233091 в сообщении #1153924 писал(а):

Тут оценка $\[K = N - 2\]$ не работает.

slavav в сообщении #1153908 писал(а):

Так что "классические" оценки верны только если никакие три точки не лежат на одной прямой.

Если разрешить развёрнутые углы в исходных многоугольниках, то $N$, $K$ становятся вообще несвязанными. Задача обретает какой-то смысл, если вы пытаетесь связать $N$, $K$ и параметр характеризующий число (числа) точек на одной прямой (нескольких прямых). Для точек в общем положении оценка верна. Теперь точки из общего положения надо пытаться стянуть на минимальное количество прямых, с тем чтобы получить многоугольники у которых только три угла не развёрнутые.

[sa233091]

Но связанны n k m
K = N - 2 -M

[slavav]

sa233091 в сообщении #1153996 писал(а):

Но связанны n k m
K = N - 2 -M

Вы наверное хотите сказать что $K \geqslant N - 2 - M$, где $N$ - число неразвёрнутых углов многоугольника, $M$ - число невыпуклых углов многоугольника, $K$ - число треугольников в триангуляции?

[sa233091]

Да, именно. И я хотел спросить а всегда ли можно разрезать на n - 2 - m?

[slavav]

Да, это всегда возможно. Попробуйте индукцию. При разрезании многоугольника надо резать так чтобы $N_1 + N_2 = N + 1$ и $M_1 + M_2 = M - 1$.

[sa233091]

Большое спасибо за ответ на вопрос