Геометрические свойства локально минимальных сетей (1097521), страница 37
Текст из файла (страница 37)
Построенное разбиение ЛХ = ~фы,ЛХ' называется разбиением на уровни выпуклости, а множество М' называется 1-ым уровнем выпуклости множества М. Если ЛХ = О~ М', то говорят, что М имеет к уровней выпуклошпи. 1исло уровней выпуклости множества ЛХ обозначим через м(ЛХ). Отметим, что множество М лежит на границе своей выпуклой оболочки, если и только если оно имеет один уровень выпуклости, который, очевидно, совпадаот с ним самим. ЛХы покажем, что число вращения произвольного локально минимального бинарного дерева Г нс превосходит 12(м(дГ) — Ц + 5.
Данное неравенство существенно ограничивает возможные топологии минимальных бинарных деревьев, Более того, см. ниже раздел 4.5, оказалось что число вращения так же хорошо работает и в случае бинарных деревьев, локально минималь- Глава 4. Плоские локально минимальные деревья.
168 ных относительно произвольного функционала взвешенной длины [39], В недавней совместной работе [52, 53] автор и А. А. Тужилин с помощью понятия числа вращения получили нетривиальные ограничения на топологии произвольных [не обязательно бинарных) минимальных деревьев, а также ряд интересных результатов, касающихся локально минимальных параметрических сетей [см. ниже раздел 4.4). Отметим здесь жс, что разработанный в [52, 53] подход имеет и самостоятельный интерес с точки зрения изучения геометрии плоских деревьев [не обязательно минимальных), все ребра которых представляют собой прямолинейные отрезки. Такие плоские деревья мы будем называть линейными.
Действительно, основная теорема раздела 4.4 сформулирована без всяких предположений о минимальности. В такой постановке задача была предложена автору О. Р. Мусиным во время обсу.жденил результатов автора ,'38, 39]. Автор пользуется слу.чаем поблагодарить О, Р, Мусина и всех участников его семинара за интересное и содержательное обсуждение. Мы начнем эту главу. с разработки технического аппарата, который позволит нам работать с ломаными на плоскости. Наш интерес к ломаным объясняется тем, что каждый путь в плоском локально минимальном дереве, очевидно. является ломаной. 4.1 Плоские ломаные 1: случай общего по- ложения В данном разделе мы введем необходимые определения и обозначения, и подробно изучим геометрию пары ломаных, соединяющих две фиксированных точки плоскости.
При этом мы будем предполагать, что эти ломаные находятся "общем положении". В дальнейшем, см. раздел 4.3, мы откажемся от этого предположения. Напомним определение ломаной. Определение. Конечныи набор прямолинейных отрезков [АО Аыы] = Ь„1 = О,..., и — 1, называется незамкнутой ломаной, если все точки А, попарно различны, а интервалы [А„А,л1) попарно не пересекаются и не содержат точек Аь, к = О,..., и. Конечное множество отрезков А = [А;, Ар~О ~„л „], ~ = О,...., и — 1 называется замкнугаой лол1аной, если все точки А; попарно различны, а интервалы [А„АО 1~,„,о „) попарно не пересекаются и не содержат точек Аы й = О,...,п — 1, Отрезки [АоА,~1] называются ребрами ломаной, а точки А, ее вершинами.
Если ломаная незамкнута, то вершины Ао и А„называ- 4.1. Плоские ломаные 1. ются концевыми, а все остатьные --. внутренн ми вершина,ни ломаной. Лалее, если ломаная Ь незамкнута, то ее ребра ~Ап Лью ] при 1 = О, и — 1 называются концевыми ребрами, а все остальные внутренними ребрами ломаной В. Если же ломаная В замкнута, то все ее вершины и ребра называются внутренними. Ломаная В' называется по0ломаной ломаной ь, если каждое ребро ломаной 1,' является также и ребром ломаной В, Если ломаные В' и В совпадают как подмножества плоскости, но 1' содержит некоторые дополнительные вершины, то Ь' называется иэмельчением ломаной С. Отметим, что, по опрсделению, каждая ломаная представляет собой вложенную кусочно-гладкую (даже кусочно-линейную) кривую на плоскости.
В дальнейшем нам будет удобно использовать следующие обозначения. Если В незамкнутая ломаная, а .4 и В две се произвольные точки, то через 1~А,В] обозначим часть 1, между Л и В. Если из 14А, В] выброшона точка, Л или В, то заменим соответствующую квадратную скобку "[" или "]" на круглую, "(л или ")". Замечание. В дальнейшем, говоря о ломаных, мы, допуская определенную вольность речи, иногда будем подразумевать их "естественные' измельчения,которые очевидно определяются из контекста. Например, если некоторая ломаная 1',как подмножество плоскости, содержится в ломаной В, то мы будем говорить, что В' является подломаной ломаной В,хотя формально это верно лишь для измельчения ломаной Ь, полученного добавлением ко множеству сс вершин всех вершин ломаной ь'. 4.1.1 Твистинги и кручение Пу.сть В произвольная ломаная. По определению, все ее вершины А, канонически перенумерованы..Ясно, что каждая ломаная может быть задана занумерованным набором своих вершин.
Если перенумеровать точки А; в противоположном порядке, то мы снова паяучим ломаную, которая совпадает с исходной, как подмножество плоскости. Выбор одной из двух канонических ну.мсраций вершин ломаной В называется ориентацией ломаной Ь, Если ориентация ломаной В фиксирована, то можно рассматривать каждое звено .4,Аьы ломаной В как вектор с началом в А, и концом в А;+г Напомним, что если (а, Ь) упорядоченная пара линейно независимых векторов на плоскости, на которои раз и навсегда фиксирована 170 Глава 4.
Плоские локально минимальные деревья. ориентация, то можно определить ориентированныв угол о(а, Ь) от о, к Ь так. Величина о(а, Ь) равна величине меньшего из двух углов между векторами, а знак знаку ориентированного репера ~а, Ь). Если векторы а и Ь сонаправлены, то ориентированный угол также определен и равен нулю. Для противонаправленных векторов ориентированный угол не определен. В дальнейшем, нам будет удобно нормировать ориентированный угол. Определение. Твистингом ьъ" (а, Ь) упорядоченной пары векторов а и Ь назовем число сь(а, Ь)/(и/3).
Итак, пусть 1, ориентированная ломанал, и а, = ~А,,А,е1), 1 = О,..., и — 1 ее последовательные ребра (если ломаная замкнута, то сложение в индексах понимается по модулю и). Определение. Твистингом си А, вершины А; назовем твистинг между последовательными векторами-звеньями. инпидентными Аб т,е, число ьи (а; ма;). Отметим, что в случае незамкнутой ломаной твистинг определен лишь для внутренних вершин. Предположим теперь, что ломанал Т, незамкнута.
Определение. Сумма твистингов всех внутренних вершин ориентированной ломаной Т называется кручением вдоль 7, и обозначается через сп А: о — 1 Сп7 = ~ ьпА,. г=! Если ломаная Т состоит из одного звена, то положим си 1, = О. Легко видеть, что кручение вдоль незамкнутой ориентированной ломаной Т обладает следующими свойствами; ь если заменить ориентацию ломаной Т, на противоположную. то кручение вдоль Т изменит знак (косая симметрия): ° если ломаная 1,' получена из Т. измельчснием, то кручения вдоль Х и 1,' совпадают: ° если А,; произвольная внутренняя вершина Х„а 71 и Тз ориентированные в соответствие с ориентацией 7.
ломаные, на которые А, разбивает Т,. то тп Т, = ьп |1 + 1п А, + 1п 1з., 4.1. Плоские ломаные 1. 171 ° если Р --. произвольная точка, лежащая внутри произвольного ребра из Ь, а Х1 и Х я -- ломаные, на которые Р разбивает Хо ориентированные в соответствие с ориентацией А,то 1пЕ = 1п Х,, + 1пЛа (аддитивность). Пусть теперь Х, замкнутая ориентированная ломанал. Определение.
Сумма твистингов всех вершин из Х называется кру- чением вдоль за кнутой ломаной Х и обозначается через Сссрл ь — 1 1пХ = ~спАь с=о Сформулируем несколько очевидных свойств кручения вдоль замкнутой ориентированной ломаной Л. ° Если заменить ориентацию ломаной Х на противоположную, то кручение вдоль Х изменит знак (кососихсметричность). ° Если ломаная Е' получена из Х измельчением, то кручения вдоль Х и ь' совпадают.
° Если А, произвольная вершина Л, и Л' незамкнутая ломаная, полученная из Х разрезанием по А„и ориентированная в соответствие с ориентацией Хь то сп Х = Сп Х' + сьс Аь Более точно, чтобы получить ломаную Ь' из ломаной Хь следует выбросить из Х малую (связную) окрестность Гл с Г точки А, не содержащую вершин ломаной Хо отличных от точки Аь если А, вершина. ° Если Р произвольная точка лежащая внутри произвольного ребра из Хь и П вЂ” незамкнутая ломаная, полученная из Х разрезанием по Р и ориентированная в соответствии с ориентацией Х. то гнЬ = 1пХ,'. Следующее предложение непосредственно вытекает из определений.
Предложение 4.1 Пусть Х вЂ” про звольная замкнутая ломаная, ориентированная против часовой стрелки. Тозда сиХ = 6. Если жс Х ориентирована по часовой стрелке, то 1пЛ = — 6. В дальнейшем нам также понадобится следующее понятие деформации ломаной. 172 Глава 4. Плоские локально минимальные деревья. Определение. Семейство ломаных Т <, 1 6 [0< 1], с вершинами в точках А,', где 1 = О,..., и+ 1., называется деформацией ломаной 1 = То, если все кривые А,' непрерывны.
Часто деформацию произвольного измельчения ломаной Т мы также будем называть деформацией ломаной Ь, опускал слово 'измельчение". Вершина А, ломаной Ь называется неподвижной при деформации Т<, если Л< = Л, для любого 1 е [О, 1]. Все остальные вершины называются подвижными. Ребро [А<,.4<+<] ломаной Т,, называется подвижным, если подвижна хотя бы одна из его вершин. Множество всех подвижных ребер из Т называется носшпелем деформации Т<. .Чегко доказывается следующее предложение. Предложение 4.2 Пусть Ь< произвольная деформация ориентированной ломаной Т.. Гели Т, незамкнутпаь то предположим дополни<полено, что направления первого и последнего ее звеньев не меняю<вся в процессе деформации.
Т<ида кручение вдоль Т, не меняегпся при деформации< 1пТ' = сопвс = 1пЬ, г Е [0,1]. Доказательство. Действительно, из определения кручения вдоль ломаной немедленно вытекает, что в процессе описанной деформации кручение ломаной У не меняется с точностью до [3,<х)2йх = бв.. С другои стороны, очевидно, кручение 1п 1 ' деформируемой ломаной непрерывно зависит от 1, откуда и вытекает требуемое утверждение. Доказательство закончено. 4.1.2 Пара ломаных в общем положении Пусть 1' и 1.~ -- две ломаные, некоторые вершины которых фиксиро- ваны. Определение. Будем говори~в, что Ь< и Тз находятся в общем положении, если они пересекаются не более чем в конечном числе точек, каждая из которых или не является вершиной ни одной из ломаных, или яатяется фиксированной вершиной одной из Ь<. Пусть теперь 1 ~ и 1 ~ некоторые ломаные.
Предположим, что эти ломаные находятся в общем положении. Выбросим из Хз все точки пересечения с ь<, и обозначим через 7~2 замыкания полученных последовательных связныхкомпонент, Ясно, что Ь являютсяломаными. Если 2 ломаная Х- 'ориентирована, то будем предполагать что компоненты < з занумерованы в соответствие с ориентацией ломаной 1.г. 4.1. Плоские ломаные 1. 173 Определение.
Построенное разбиение Ез = Ой! назовем канониче- ским раобиениемз ломаной Вз по отношению к В!. Предположим теперь, что лолганые В' и В- соединяют фиксированные точки А и В и находятся в общем положении. Пусть л 3 = 'го~ Ь-'. каноническое разбиение Вз относительно Ь!. Ориснтируем обе ломаные В! и Вз от А к В. Каждая ломаная Вл, вместе с соответствующей частью ломаной Вг, ограничивает некоторую ограниченную область й; на плоскости. Более точно, если А и В .-- начальная и конечная вершины ломаной Вз, и 6 часть ломаной В! между А. и Вм то область й ограничена замкнутой ломаной Хз 0 дг Ломаную 6, будех! называть основанием области 11,, а сами области П, П- областлльи, Первая и последняя из П называются концевыми, а все остальные - внутренними й-областями. Выбранная ориентация ломаной Ез определяет положительное направление движения вдоль 4,9 и, следовательно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
