2014 dxdy logo

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

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



Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Лемма о диагонали
Сообщение20.04.2017, 21:55 


11/08/16
172
В олимпиадных задачах на многоугольники (особенно использующих принцип индукции) часть используется такое утверждение (лемма о диагонали) о том, что в любом невыпуклом многоугольнике найдется диагональ лежащая внутри этого многоугольника.
Я знаю несколько (схожих) доказательств этого факта (одно из них есть в той же "Планиметрии" Прасолова), но не знает ли кто более простого и короткого доказательства?

 Профиль  
                  
 
 Re: Лемма о диагонали
Сообщение20.04.2017, 23:05 
Заслуженный участник
Аватара пользователя


09/09/14
4652
Посмотрите здесь лемму в начале решения задачи ММ148. Оно не короче, чем у Прасолова (куда уж короче!), но заходит со стороны выпуклой вершины, что чуть привычнее для интуиции.

 Профиль  
                  
 
 Re: Лемма о диагонали
Сообщение21.04.2017, 20:38 


26/05/14
468
Замечательная задача. Существование триангуляции показать намного сложнее чем потом показать что в любой триангуляции не менее двух ушей (ухо - пара соседних сторон стянутых диагональю). Хочется доказать напрямую, но не знаю как.

Я обычно доказываю, так как сделано в приведённой ссылке. Но есть другой путь. Кому-то он покажется проще.
Если многоугольник выпуклый наличие диагонали очевидно.
Пусть многоугольник не выпуклый. Найдём вогнутую вершину. Из неё пустим луч внутрь многоугольника. Получили функцию $k(\alpha)$ - номер ближайшего отрезка пересечённого лучом пущенного под углом $\alpha$. Можно показать что $k$ не константа на своей области определения. Найдём $\alpha_0$ в которой $k$ меняется. Кусочек нашего луча в этом направлении и есть диагональ.

Тоже много дыр и дырочек.

 Профиль  
                  
 
 Re: Лемма о диагонали
Сообщение22.04.2017, 18:22 
Заслуженный участник


27/06/08
3124
Волгоград
slavav в сообщении #1211407 писал(а):
Тоже много дыр и дырочек.
Вот (на мой непритязательный взгляд) рассуждение без особых дырочек:
Цитата:
Докажем, что из каждой вершины угла, больше развернутого, выходит хотя бы одна внутренняя диагональ. Для этого проведем из этой вершины произвольный луч во внутреннюю область многоугольника. Этот луч обязан пересечься с границей многоугольника. Точек пересечения может быть и не-сколько, но нас интересует ближайшая к началу луча. Если эта точка окажется вершиной много-угольника, то искомая внутренняя диагональ найдена. Если же эта точка лежит на стороне, начнем вращать луч вокруг начала, например, против часовой стрелки. Рано или поздно луч встретится с какой-либо вершиной многоугольника (она не обязана лежать на стороне, в которую первоначально «уперся» наш луч) или начало луча перестанет лежать внутри многоугольника и пойдет по его стороне. В первом случае мы уже нашли искомую диагональ. Если же начало луча перестанет лежать внутри многоугольника, вернемся к начальному положению и будем вращать луч теперь по часовой стрелке. В силу того, что внутренний угол при вершине, из которой мы стартовали, больше развернутого, мы не можем второй раз дойти до положения, когда начало луча, проходит по стороне треугольника, до того как наш луч встретится с какой-либо вершиной. Это и даст нам искомую диагональ.
Это отрывок из авторского решения MM148. Не исключаю, что у Прасолова так же, не смотрел. :oops:

 Профиль  
                  
 
 Re: Лемма о диагонали
Сообщение22.04.2017, 19:42 
Заслуженный участник


11/05/08
31279
grizzly в сообщении #1211188 писал(а):
Посмотрите здесь лемму в начале решения задачи ММ148. Оно не короче, чем у Прасолова (куда уж короче!), но заходит со стороны выпуклой вершины, что чуть привычнее для интуиции.

У Прасолова, как мне кажется, пробел есть. Он говорит о точках, в которых сменяются видимые стороны или части сторон. Подразумевая, что среди этих точек обязательно найдётся хоть одна вершина. По-моему, это требует обоснования. Т.е. хоть какие-то заклинания, но нужны.

Я бы оформил это так. Из невыпуклой вершины $A$ со смежными сторонами $AB$ и $AC$ выводим какой-нибудь внутренний луч (ну хоть по биссектрисе) и фиксируем его ближайшую точку $M$ пересечения с границей. Если это вершина, то финиш, поэтому считаем, что это внутренняя точка некоторой стороны. Берём тот из концов этой стороны $D$, который не совпадает ни с $B$, ни с $C$. Если внутри треугольника $DAM$ и на интервале $DA$ нет точек границы, то $DA$ -- внутренняя диагональ, поэтому предположим, что такие точки есть. Среди них обязательно есть вершины, т.к. любая сторона, часть которой лежит внутри треугольника, не может пересекать ни $DA$, ни $DM$ и, следовательно, по крайней мере в одном направлении заканчивается внутри треугольника. Берём ту из этих вершин $K$, проходящий через которую луч $AK$ ближе всего к лучу $AM$, а если на этом луче несколько вершин, то берём ближайшую к $A$. Тогда на интервале $AK$ точек границы нет: ими могли бы быть лишь внутренние точки сторон, пересекающих $AK$, но любая такая сторона заканчивалась бы вершиной, лежащей внутри сектора $KAM$, т.е. соответствующий луч оказался бы ближе к $AM$..

Надеюсь, мне удалось избежать соблазна непрерывности.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 5 ] 

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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