Лемма о диагонали

[sa233091]

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

[grizzly]

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

[slavav]

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

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

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

[VAL]

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

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

Вот (на мой непритязательный взгляд) рассуждение без особых дырочек:

Цитата:

Докажем, что из каждой вершины угла, больше развернутого, выходит хотя бы одна внутренняя диагональ. Для этого проведем из этой вершины произвольный луч во внутреннюю область многоугольника. Этот луч обязан пересечься с границей многоугольника. Точек пересечения может быть и не-сколько, но нас интересует ближайшая к началу луча. Если эта точка окажется вершиной много-угольника, то искомая внутренняя диагональ найдена. Если же эта точка лежит на стороне, начнем вращать луч вокруг начала, например, против часовой стрелки. Рано или поздно луч встретится с какой-либо вершиной многоугольника (она не обязана лежать на стороне, в которую первоначально «уперся» наш луч) или начало луча перестанет лежать внутри многоугольника и пойдет по его стороне. В первом случае мы уже нашли искомую диагональ. Если же начало луча перестанет лежать внутри многоугольника, вернемся к начальному положению и будем вращать луч теперь по часовой стрелке. В силу того, что внутренний угол при вершине, из которой мы стартовали, больше развернутого, мы не можем второй раз дойти до положения, когда начало луча, проходит по стороне треугольника, до того как наш луч встретится с какой-либо вершиной. Это и даст нам искомую диагональ.

Это отрывок из авторского решения MM148. Не исключаю, что у Прасолова так же, не смотрел.

[ewert]

grizzly в сообщении #1211188 писал(а):

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

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

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

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