Сложный вариант осеннего тура Турнира Городов

(a) Проведем доказательство индукцией по База для тривиальна. Пусть в угольнике с помощью flip-ов можно получить все триангуляции. Докажем это утверждение для угольника. Пусть — наш угольник. Заметим, что проведена хотя бы одна диагональ Иначе, если ни одной такой диагонали не проведено, то найдется диагональ где Рассмотрим диагональ между вершинами с минимальным Тогда между вершинами не проведено ни одной диагонали. Так как то получаем, что наше разбиение многоугольника диагоналями не является триангуляцией — противоречие. Итак, хотя бы одна диагональ проведена между вершинами для некоторого Она отсекает от нашего многоугольника треугольник Весь многоугольник без этого треугольника обозначим (он получается удалением вершины из и ребер, соединенных с ней). Тогда — выпуклый угольник. Любое его разбиение может быть получено flip-ами треугольников в его триангуляции. Вернемся к многоугольнику С помощью нескольких flip-ов можно вместо диагонали получить любую диагональ Если такая диагональ получена, то рассуждения о получении триангуляций с этой диагональю аналогичны рассуждениям с диагональю Таким образом, любая триангуляция получится, поскольку любая триангуляция содержит диагональ между некоторыми вершинами и

(b) Рассмотрим соседние вершины и Обозначим через разбиение, в котором все диагонали выходят из вершины а через — разбиение, в котором все диагонали выходят из Заметим, что в ни одна диагональ не выходит из Поскольку за одну перестройку добавляется не более одной диагонали, выходящей из то для преобразования в требуется не менее перестроек.

(c) Предположим, что мы хотим преобразовать в где и — два произвольных разбиения. Пусть — вершшна, из которой выходит хотя бы одна диагональ — перестройка, определенная в (b). Покажем, что можно преобразовать в добавляя при каждой перестройке по одной диагонали, выходящей из Пусть диагональ ещё не проведена. Тогда её начало принадлежит одному из треугольников разбиения, причем — диагональ. Поэтому к ней с другой стороны прилегает некий треугольник разбиения ( может совпадать с Сделав flip четырёхугольника мы добавим диагональ Итак, для указанного преобразования нужно не более перестроек. Для преобразования в необходимо столько же flip-oв, сколько для обратного преобразования в то есть не более поскольку одна диагональ уже стоит на своём месте.