2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Разрезание на треугольники
Сообщение23.09.2016, 11:38 


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

-- 23.09.2016, 11:40 --

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

 Профиль  
                  
 
 Re: Разрезание на треугольники
Сообщение23.09.2016, 11:56 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Разрезание на треугольники
Сообщение23.09.2016, 12:42 


11/08/16
193
gris в сообщении #1153857 писал(а):
Как-то не очень хорошо звучит в Вашем случае: улучшить оценку типа "не менее". Вроде бы она улучшается путём отодвигания левой границы вправо, но в любом разрезании количество треугольников всегда можно запросто увеличить на один. А цель состоит в отодвигании левой границы влево :?:

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

 Профиль  
                  
 
 Re: Разрезание на треугольники
Сообщение23.09.2016, 13:03 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Разрезание на треугольники
Сообщение23.09.2016, 13:58 
Заслуженный участник


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

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

 Профиль  
                  
 
 Re: Разрезание на треугольники
Сообщение23.09.2016, 14:09 
Заслуженный участник


27/04/09
28128
Я так и не понял, что за невыпуклые и выпуклые углы такие.

 Профиль  
                  
 
 Re: Разрезание на треугольники
Сообщение23.09.2016, 14:13 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Разрезание на треугольники
Сообщение23.09.2016, 14:25 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Разрезание на треугольники
Сообщение23.09.2016, 14:27 


11/08/16
193
Пусть дан 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\]$ не работает.

 Профиль  
                  
 
 Re: Разрезание на треугольники
Сообщение23.09.2016, 14:43 
Заслуженный участник


26/05/14
981
sa233091 в сообщении #1153924 писал(а):
Тут оценка $\[K = N - 2\]$ не работает.
slavav в сообщении #1153908 писал(а):
Так что "классические" оценки верны только если никакие три точки не лежат на одной прямой.

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

 Профиль  
                  
 
 Re: Разрезание на треугольники
Сообщение23.09.2016, 18:23 


11/08/16
193
Но связанны n k m
K = N - 2 -M

 Профиль  
                  
 
 Re: Разрезание на треугольники
Сообщение23.09.2016, 18:36 
Заслуженный участник


26/05/14
981
sa233091 в сообщении #1153996 писал(а):
Но связанны n k m
K = N - 2 -M
Вы наверное хотите сказать что $K \geqslant N - 2 - M$, где $N$ - число неразвёрнутых углов многоугольника, $M$ - число невыпуклых углов многоугольника, $K$ - число треугольников в триангуляции?

 Профиль  
                  
 
 Re: Разрезание на треугольники
Сообщение23.09.2016, 18:39 


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

 Профиль  
                  
 
 Re: Разрезание на треугольники
Сообщение23.09.2016, 18:57 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Разрезание на треугольники
Сообщение23.09.2016, 20:52 


11/08/16
193
Большое спасибо за ответ на вопрос

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 28 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: vicvolf


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group