Более интуитивное доказательство теоремы Зоны?

Теорема о зоне гласит, что если мы нанесем на карту расположение n линий с другой линией, общая сложность ее зоны , множества смежных с ней 0-, 1- и 2-граней, будет O (n). Фактическая константа примерно равна 6n, по крайней мере, как указано в различных учебниках, и доказательство по индукции с достаточно осторожным аргументом зарядки.

Мне задали этот вопрос в классе, и у меня нет ответа:

Есть ли альтернативное, более интуитивное доказательство теоремы Зоны?

Теперь я понимаю, что многие люди находят индукцию довольно интуитивной и будут оскорблены моим подтекстом, и готовы изменить вышесказанное, чтобы просто «заменить» их. Но есть ли такие доказательства? Или даже доказательство из книги ?

Это не чище, но это хорошая подготовка к более сложным вещам, и это хороший пример абстракции ...

Можно использовать аргумент последовательностей Давенпорта-Шинцеля. Рассмотрим регион выше линии вашей зоны. Каждая линия становится лучом, а на самом деле - двумя лучами, поскольку мы рассматриваем левую и правую стороны как разные. Сканируйте границы этой зоны слева направо, записывая, с какими лучами вы сталкиваетесь. Это последовательность, определенная более 2n символов, и шаблон abab недопустим. Таким образом, длина последовательности составляет не более 2 (2n) -1 = 4n-1. Применяя его к зоне ниже линии, подразумевается граница вида 8n.

Теперь доказать, что последовательность символов без ... a..b..a..b ... как подпоследовательность из n символов имеет длину 2n-1, легко. действительно, рассмотрим два последовательных появления одного и того же персонажа, которые ближе всего друг к другу в этой последовательности. Очевидно, что между этими двумя символами каждый символ должен быть уникальным. Рассмотрим такой символ и заметим, что если он появится где-либо еще в строке, мы получим запрещенную подпоследовательность. Таким образом, этот символ появляется ровно один раз в строке. Удалите его и при необходимости удалите дополнительный символ, если вы создали два последовательных идентичных символа. А именно, удаление символа из строки сокращает его на 2, поэтому максимальная длина строки составляет 2n-1.

Я нахожу индукцию довольно интуитивным и оскорблен твоим подтекстом. Но какой зарядный аргумент?

Wlog предполагает, что линия, определяющая зону, горизонтальна (иначе вращается), и что линии находятся в общем положении (иначе они нарушают и усложняют зону). Удалите одну из других n строк. Классифицируйте края результирующей зоны как левую или правую границы, в зависимости от того, находится ли зона справа или слева соответственно. (Некоторые ребра имеют как левую, так и правую границы, но они учитываются дважды в границе сложности.) По индуктивной гипотезе, существует не более 3n-3 левых границ. (Базовый случай n = 0 тривиален.) Повторная вставка удаленной строки добавляет не более 3 левых границ (одну на самой строке и две от разбиения более старых левых границ). Таким образом, общее количество левых границ не более 3n. Симметрично, количество правых границ не более 3n, поэтому общая сложность зоны не более 6n.

Доказательство с помощью аргумента обвинения изложено в качестве упражнения (вместе с пошаговыми подсказками) на странице 13 раздаточных материалов класса вычислительной геометрии Дэвида Маунта: http://www.cs.umd.edu/class/fall2005/cmsc754/Handouts/ cmsc754-handouts.pdf