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

[gris]

$n=5;m=1;k=5-2-1=2.$

Разве можно разрезать на два треугольника?
Или имеется в виду, что обязательно существует многоугольник $(5,1)$, который можно разрезать на два треугольника?

[slavav]

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

Разве можно разрезать на два треугольника?

Вы правы - нельзя. Я ошибся когда выписывал индукционный шаг.

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

Или имеется в виду, что обязательно существует многоугольник $(5,1)$, который можно разрезать на два треугольника?

В такой формулировке я могу сохранить лицо. Разрезание проводится как продолжение стороны прилежащей к невыпуклому углу. Если это продолжение попадёт в другую вершину, то индукционный переход возможен.

[gris]

Не уменьшение оценки может быть можно доказать от противного? Допустим, что существует $(n,m)$ многоугольник, который можно разрезать Меньше, чем на $n-2-m$ треугольников. Возможно ли предложить некоторый механизм передвижения вершин, чтобы превратить его в выпуклый при сохранении триангуляции?

[sa233091]

Ну можно <<вывернуть>> его невыпуклые углы и тогда это ничего не даст)

[VAL]

Посмотрите ММ148. Из ее решения понятно, что любой n-угольник можно разрезать на $n-2$ треугольника. Если все разрезы идут только по диагоналям, то это число нельзя уменьшить.
В задачах XV и XX туров Математического марафона рассматриваются и другие вопросы, связанные с разрезанием многоугольника на треугольники.

[slavav]

VAL в сообщении #1155091 писал(а):

Посмотрите ММ148.

Вы указали на другую задачу, более строгую. В обсуждаемой здесь задаче после триангуляции разрешено объединять треугольники если их объединение является само треугольником. За счёт этого появляется слагаемое $-M$.

[VAL]

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

Вы указали на другую задачу, более строгую. В обсуждаемой здесь задаче после триангуляции разрешено объединять треугольники если их объединение является само треугольником. За счёт этого появляется слагаемое $-M$.

Я и не утверждал, что это та же задача.

Что же до исходной, то утверждение, что любой n-угольник, имеющий ровно $m$ углов больше развернутого, можно разрезать на $n-2-m$ треугольников, очевидно, не верно. Даже ели заменить квантор на "существует", все равно будет неверно. Достаточно рассмотреть невыпуклый четырехугольник.
Если разрешить объединять треугольники после триангуляции, то ответ давно известен: любой многоугольник можно разрезать на треугольники, из которых можно сложить один треугольник (теорема Бойяи-Гервина).

Или я чего-то таки не понял в условии.

[slavav]

Вы правы по поводу $n - 2 - m$. Скорее всего можно пытаться доказать что приведённая оценка не уменьшается. И что для многих пар $n$ и $m$ достигается.

Объединять треугольники нужно не двигая их.

[VAL]

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

Вы правы по поводу $n - 2 - m$. Скорее всего можно пытаться доказать что приведённая оценка не уменьшается. И что для многих пар $n$ и $m$ достигается.

... для некоторых n-угольников.

Цитата:

Объединять треугольники нужно не двигая их.

Тогда заем резать?

[slavav]

Оценка $n - 2$ для числа треугольников верна только для классической задачи триангуляции, когда вы строите все возможные диагонали. Если этого требования нет, то количество треугольников может быть меньше. Пример: треугольник с произвольным числом вырожденных вершин на одной стороне триангулируется в один треугольник, а диагоналей в нём $n - 3$.

[VAL]

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

Оценка $n - 2$ для числа треугольников верна только для классической задачи триангуляции, когда вы строите все возможные диагонали. Если этого требования нет, то количество треугольников может быть меньше. Пример: треугольник с произвольным числом вырожденных вершин на одной стороне триангулируется в один треугольник, а диагоналей в нём $n - 3$.

Допустимость вырожденных вершин - вопрос договренности.
Например, в упомянутых выше задачах XV и XX туров мат. марафона специально оговаривалось отсутствие таких вершин.
А в этом топике данный вопрос не поднимался.

[slavav]

VAL в сообщении #1155265 писал(а):

Допустимость вырожденных вершин - вопрос договренности.
Например, в упомянутых выше задачах XV и XX туров мат. марафона специально оговаривалось отсутствие таких вершин.
А в этом топике данный вопрос не поднимался.

Согласен, что мой пример искусственный. Вот другой пример в котором обычная триангуляция отличается триангуляции с объединёнными треугольниками:

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

[VAL]

VAL в сообщении #1155265 писал(а):

Согласен, что мой пример искусственный. Вот другой пример в котором обычная триангуляция отличается триангуляции с объединёнными треугольниками:

Ну, да. Я его видел в этой теме.
Кроме того подобных примеров полно в задачах, на которые я ссылался. В частности в ММ197