Геометрические свойства локально минимальных сетей (1097521), страница 51
Текст из файла (страница 51)
Если же концевой сингулярный элемент не совпадает с соответствующей концевой вершиной (т.е. является касательным), то отнесем этот элемент к А-элементам, если он содержит точку А, и к В-элементам в противном случае. Отметим, что сингулярный элемент не может содержать сразу обе точки А и В, так как ломаные Ь' и Ь~ по предположению не совпадают как подмножества плоскости. Таким образом., построено разбиение множества всех элементов канонического разбиения на четыре класса, Построим теперь по паре ломаных ь' и ьз некоторое слово. Пусть Ез = Ок А, каноничсское разбиение ломаной Лэ относительно 1.1, где через Л, обозначены последовательно занумерованные элементы канонического разбиения (как регуллрные,так и сингулярные).
Причж14Ы) пишем теперь каждому элементу Ь, букву Х, Я *, где буква Х, равна А, В, Е или Е в зависимости от того, к какому классу. принадлежит элемент Л„и в18п(Ь,) знак этого элемента, определенный выше. Составим слово И'(ь"-, Г,1), записав полученные буквы по порядку: 14;~Еэ Е1~ ХМРЦФО Хч яч(~ и) 1 л' Определим вес слова $Г(Ьз, Ь~) как сумму степеней всех входящих в него букв, и обозначим его через чче1фй(ьз.,ь1). Буквы, входящие в слово в нулевой степени, договоримся не писать. Непосредственно из определений вытекает следующее утверждение. утверждение 4.8 Во введенных вьпие обозначениях, ~(Ех Е1) тД; ч~(Е2 Е1) Напомним, что в случае общего положения нами были получены оценки на индекс ломаной Ь~ по отношении> к Ь~ в терминах количества А- и В-элементов, см.
следствие 4.3. Чтобы получить аналогичные оценки в общем случае, нам понадобится следующее утверждение. 4.3. Плоские ломаные П. 233 Ъ'тверждение 4.9 Пусть Ь' и Ез -- пара произвольных не совпадающих ломаных, соединяющих точки А и В. Пусть Ф~ .- правильная регуляраэующая деформация ломаной Бз относительно Т,'. Тогда количества А-, В- и Е-элементов, образованных ломаной ьз по огпношению к Б~, совпадают с соответствующими количествами А-, В- и Р-элементов, образованных ломаной Ф,(Бэ) по отношению к Е'. Доказательство. В самом деле, отметим, что только регулярные элементы и концевые касательные сингулярные элементы не являются пустыми.
При правильной регуляриэующей деформации Ф~ каждый внутренний сингулярный элемент порождает не более одного регулярного элемента, который является пустым, и нс порождает крайних элементов. Далее, крайний сингулярный А- или В-элемент порождает при деформации Фе регулярный .4- или В-элемент соответственно, Наконец, регулярные элементы не переходят из класса в класс при регуляриэуюшей деформации. Доказательство закончено, Иэ утверждения 4.9, следствия 4.3, и того факта, что 1пс1(Ьэ, Б1) = 1пс1(Фе(Ьз), Е') по опРеделению дефоРмации Фо полУчаем следУющие оценки на индекс.
Пусть Л~ и Л~ различные ломаные линии с общими концевыми вершинами А и В. Пусть, как и выше, Ф - — это регуляризуюшая деформапия ломаной ьз. Обозначим через Ф(Бг) ломаную., редуцированную иэ Ф(Бз) (напомним, что Ф(Ьз) и Ль в общем положении). Следствие 4.10 В сделанных выше обозначениях, рассмотрим канонические разбиения ломаных Ез и Ф(Бз) относительно Ьь. Пусть р и у количества А- и В-элементов канонического разбиения исходной ломаной Л относительно Ь . Тогда ~1п4Б2, Б')~ < р+ у+ 1.
Более того, ° если канонические разбиения ломаных Ьз и Ф(Ьз) не содержат Е-элементов, то ° если каноническое разбиение ломаной Ьз не содержит Р-элемента, а каноническое разбиение ломаной Ф(ЕЯ) содержит Р-элемент, то ) шд(~,з, Б') ) < р+ у — 1. Глава 4. Плоские локально минимальные деревья. 234 В заключении данного раздела мы приведем еще несколько полезных оценок на кручение ломаной Е, концевые точки А и В которой расположены на замкнутой ломаной И', ограничивающей выпуклый многоугольник о. Обозначим через И' и И' те ломаные, на которые точки А и В разбивают Иг. Предположим, что ломаная В не содержится целиком в И', в частности, Ь не совпадает ни с И'', ни с И'~.
Имеет место следующий аналог следствия 4,4. эгтверждение 4.10 В сделанных предполоэхениях, имеет место сле- дующее неравенство: (упВ~ <3/1п11Т,,И™)+1п<1(В,14з)/+6. Доказательство. Ориентируем ломаные И" и И'з от А к В. В силу предложения 4.16, имеем: спй = 1пИ" + 61пс1(А,Ит') — о(Е,И") —,6(У,И"), сп Е = сп И' + 6 1по(Х,, И~а) — о(А, И' ) —,о (Ь, И'" ) .
Рассматривая те же два случая, что и в доказательстве следствия 4.4, получим следующие неравенства для капиевых твистингов; ~о(Е,И")+о(Ь,Игз)~ < 3+~ 1иА~ и ~6(Л,Иг')+ДЕ,Игз)~ < 3+~1иВ~. Кроме того, так как И' ограничивает выпук.лую область, ( сп И" + уп И -'! + ( си А! + ) сж В( < 6. Теперь, складывая первые два равенства и используя сделанные выше оценки, получаем требуемое. Нам также понадобится следующая модификация только что доказанного утверждения. В обозначениях утверждения 4.10, рассмотрим каноническое разбиение В = ОЛ, ломаной В относительно И'.
Предположим, что концевой сингулярный элемент Ь~, содержащий точку А, нс совпадает с точкои А, и, для определенности, является подломанои ломаной Ич. Как и вьппе, будем предполагать, что В у И', поэтому, в частности, Ь| ~ И''. Для краткости, обозначим концевой сингулярный элемент Тч через К, и пусть А' концевая вершина ломаной 1, отличная от А. Обозначим через Х и И" ломаные, полученные соответственно из В и И' выбрасыванием подломаной 1. Далее, обозначим через И'з ломаную, полученную из 1Ф'з добавлением ломаной 1. 4.3.
Плоские ломаные П. 235 Ъ'тверждение 4.11 В сделанных предположен ях, имеет место сле- дующее неравенство: ~ Сп Х , '< 3 ~ шс1(Х, Иге ) + пн1(Х, И'г) ~ + 6. Другими слов ми, в сделанных предположениях, ари оценке кручения ломаной Х, можно перейти к ломаной Х, сингулярные концевые элементы которой совпадают с соответствующими концевыми вершинами. Доказательство. Ориентируем ломаные И'~ и И'г от А к В. В силу предложения 4.16. имеем: спХ =1п Иг + 6шс1(ХчИ' ) — о(Хч И' ) — )э1Х„И' ), 1пХ, = хи И'г + 6 1пс1(Е, И' ) — о(Х, И' ) — ~(Хч И' ). По определению индекса ломаной, шс1(Хч Иес) = а13п1Р) + пн11Х, И'~). С другой стороны, так как подломаная Р ломаной Х, пересекается с ломаной Ию только по одной точке А, то шс1(Хч Ива) = шс1(Х, И"~). Наконец, по опРеделению концевого твистинга, о(Хч И е) = Зв13п1Р).
Имея ввиду сделанные наблюденил, складывая предыдущие равенства и группируя слагаемые, получаем, что: 21пВ = 61шс1(Х, И" ) + шс11Х, И~)) — (д(Ь, И") + фХо И"-)) + + 3в13пф+ (1в И" + Уп И г — о(Х„И')). Осталось заметить, что (3(Ь, И') + 6(Е, И'~)! < 3 + (1ъ В) как и в доказательстве утверждения 4.10, где 1жВ твистинг точки В как вершины ломаной Иг ориентированной одним из двух возможных способов; далее, ~3в13п(Р) ~ = 3; и., наконец, как и в доказа,тельстве утверждения 4.10, ~ сп И" + 1п И'г ~ + ~ о1Х Руг) ~ + ~ си В ~ < 6 так как ломаные Иг' и Иг это стыкующиеся в точках А и В "половинки" границы Иг выпуклого многоугольника, а о(Хч И'~) . совпадает с твистингом в вершине А ломаной И', ориентированной одним из двух возможных способов.
Поэтому, получаем: 2)1пХ) < 6(шй(Х,И'~) + шс)(Х, И"-)) + 3+ )скВ(+ + 3 + ( св И' + 1п 14'~ ) + ( а (Хч И' ) ! < < 6(шсЦХ, Ич) + 1пс)(Х, И'г)) + 12. Разделив последнее неравенство на 2,получаем требуемое. Глава 4. Плоские локально минимальные деревья. 236 Оказывается, утверждение 4,10 можно существенно усилить, если предположить дополнительно, что ломаная Л целиком лежит в многоугольнике о. о'тверждение 4.12 Пусть Е --.
ломаная,,лежащая в вьтуклом многоугольнике о, причем предположим, что концевые точки А и В ломаной В расположены на ограничивающей многоугольник о ломаной И'. Тогда кручение ломаной А но абсолютной вслачине не превосходит, шести: ]ьпЛ] < 6. Доказательство. Для доказательства построим специальную дсформацию ломаной Ь. Пусть 1'ы..., Рь все внутренние вершины из Ь, попавшие на ломаную И'. Зададим в каждой из вершин 1г вектор и„ направленный внутрь многоугольника о. Определим деформацию Фь, 1 Е ~0, 1], ломаной Ь, сдвигая каждую из вершин 1г вдоль соответствующего вектора ь, внутрь многоугольника о. Ясно, что ломаные Фь(ь), 1 Е (О, 1], находятся в общем положении с ломаной И' при фиксированных общих концевых вершинах.
Поэтому для этих ломаных справедливо строгое неравенство: ]1п Фь(В)] ( 6, Х й (О, 1]. Кроме того, очевидно, кручение ломаной Фь(А) непрерывно зависит от й Переходя в последнем неравенстве к пределу при 1 — ь О+, получаем требуемое утверждение. 4.4 Геометрия плоских линейных деревьев В разделе 4.2 мы подробно изучили связь между числом вращения плоских локально минимальньсс бинарных деревьев и числом уровней выпуклости граничного множества. Оказывается, эта связь имеет довольно глубокие корни, Как выяснилось, аналогичный результат имеет место для произвольных линейных деревьев на плоскости. В настоящем разделе мы определим понятие числа вращения 1ъ-Г для произвольного линейного дерева Г на плоскости, а также понятие геометрической границы д„Г такого дерева.
Эти две естественных характеристики произвольного линеиного дерева оказываются связанными точно так же как в случае локально минимальных бинарных деревьев, см. предложение 4.10. При этом предложение 4.10 может быть получена как простое следствие основной теоремы настоящего раздела (сьь ниже теорему 6) и теоремы о локальной структуре минимальных бинарных деревьев. Более того, из той же теоремы 6 и теорем о локальной структуре параметрических локально минимачьных деревьев и взвешенных 4.4. Линейные деревья. 237 локально минимальных деревьев (см, главу 3) можно получить аналоги предложения 4,10 для этих классов минимальных деревьев, см. следствия 4.18, 4.20 и 4.21 ниже. Итак, основным объектом изучения данного раздела бу.дут плоские линейные деревья.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
