Классификация локально минимальных плоских сетей с выпуклыми границами (1097579), страница 32
Текст из файла (страница 32)
Доказательство. Слюва представим линейный скелет (участок) Е в виде обьсдпнсния последовательно идуплих змей Ул разных направлений, и в каждой змсс УП кроме первой, выделим ее нача.льную ячейку Ль Из всрплины прямого угла О треугольника ьлЕЕ опустллм перпендикуляр па сторону ЕЕ. Из основания этого перпендикуляра опустим перпендикуляр на сторону Г0. Далее, из основания вновь полученного перпендикуляра снова опустим перпендикуляр на ЕЕ,и т.до см.
рис. 2.23. В результате мы построим бесконс шую последовательность прямоугольных треугольников, меньший катет каждого из которых лежит или на ЕЕ, и.ш на Е0. Оти треугольники естественным образом упорядочены. Поставиьл в соответстшле последовательным выделешп,лм ячейкам лХ, последоватсльныс выдслснныс треугольники Ты л' = 2, 3,.... Легко видеть, что катет треугольпикаТ,, лежаший на стороне угла р, параллелен грани шо лу не концевому л ребру соответствуюшей ячейки з."ль Для удобства, стороны треугольников Тч не лежащие на сторонах угла Е, назовем боповыеяи, занумеруем последовательно н обозначим через а,. Отметим,что у каждого треугольника 7,' имеется две боковых стороны: ал и агут Рассмотрим произвольную ооковую сторону е треугольника Тп Квкдую прямоугольную трапецию, построенную снаружи треугольника Т; так, что сс боковые стороны лсхсат на сторонах угла Е, а одно из оснований совпадает с е, назовем прижыиаюиЛей.
Теперь иска лая минимальная рсьцлллзацлля стран гся по аналогии с тем, Ячейка зз, может оказатыя концовой, осли цослодняя змея участка 1 состоит из одной ячейки. '!еорема реализации Г Е Рис. 2.24: Минимальная реализация нс более чем лестницы в усеченном треугольнике как это дела.
тось в предыдущем разделе (см. рпс. 2,24). Разобьем скелет (участок) Е па участки двух типов: выдслснныс ячейки лм н связные компоненты паркета Е, пз которого выброшены ячейки 1хь Оти связные компоненты, очевидно, являются змеями, и, в дальнейшем, говоря о яих, мы будем называть их эжелжп, чтобы отличать от выделенных ячеек Ьь которые будем называть ячейкалпь Последовательные элементы только что построенного разбиения обозначим через Н,. Будем последовательно реализовывать последовательные элементы П, так. Элемент Ны являкяцийся, очевидно, змеей, реализуем в некоторой трапеции, примьпсаюшсй к первой боковой стороне аз, выпустив мннимальнузо реализацию змеи Н~ из произвольной внутренней точки Ез основания ез ф аз этои трапеции.
Отметим, что отростки змеи Н~ параллельны аз. При этом, выбрав трапспню достаточно узкой, можно всегда добиться того, чтобы эта минимальная реализация пришла во внутреннюю точку А стороны аз. С помощью гомотетии с центром в вершине Г угла Р, примененной к построенной примыкающей трапеции и треугольникам '1',, ! ( 2, совместим сторону ез с отрезком ЕНь При:лом точка Е перейдет в некоторую точку Х отрезка ЕВ. Ясно, что, в силу произвольности точкн Ем так мозкно получить любую внутреннюю точку из Е1Х Сохраним за продеформированными объектами тс жс обозначения. Элемент Нз, если оп есть, очевидно, является ячейкой ххз.
Построим в треугольнике уз минимальную сеть соответствукпцего направления, эквивалентную двойственному графу ячейки йз так, чтобы одной из граничных вершин этой минимальной сети являлась точка Лз, а другие две сс граничные вершины лежали на внутреяносч,ях двух других сторон треугольника Тз, отличных от аз. Легко видеть, что этого всегда можно добиться, при произвольном расположении точки Лз внутри стороны аз. При этом, если ячейка ьхз нс крайняя ячейка в 1, то сраничная вершина построенной сети, соответствуюгиая граничной всрппшс ГШ попадет на сторону угла 1'.
Обозначим через Ла грани шую вершину только что построенной ми- 'Георема реализации ннмальной сети, лежащую внутри стороны оз. '1ак как каждое внутреннее звено оси лестницы сопгоит не менее чем из двух осей ячеек, элемент Нз, сели он есть, снова является змеей. Рассмотрим достаточно узкую примыкающую к аз трапецию и, так же, как и выше, реализуем в ней змею Нз, пачипающучося в точке дз и приходяшую в некоторую внутреннюю точку Ез основания ез ф аз этой трапеции.
Применим к объединении> треугольников 7'„, ! > 3, такую гомотетию с центром в вершине Г угла Р, оставив при этом на мессе треугольник Тз, чтобы образ осз боковой стороны аз треуь ольннка Тз совместился с сз. Продолжим описанный только что процесс до тех пор, пока не будут реализованы все элементы Н,. 1!родолжим реализацию последнего концевого ребра до пересечения со сторонами угла Н.
'!ак перестроенную минимальную реализацию обозначим через Г. Отметим, что все граничные вершины сети Г лслсат на лучах т,. Обозначим через С, первую грани шую всршипу па луче т„. Тогда искомый ьетырсхугольник это СьСзРЕ. Доказательство предложения закончено. 10.5 СМ-реализация скелетов из И1Щ Цс.ль настоящего раздела пост1эопть выпуклую реализацию произвольного скелета иэ И7~~ в некотором выпуклом шестиугольнике, углы которого равны 120'. а стороны параллельны направляюшиьь паркета плоскости. Предложение 2.19 у!войственный граф произвольного отлета, принадлелсатего И;Рг, эквивалентен неконшрожу плоскому минижильному бияарножу дереву, граничные вертины которого лсзкит на гранино некоторого вьшуьлого игеетиугольники с углоаш но 120' и сньоронини, параллельнььяи паправляюи1иж паркета плоскости.
Доказательство. Из предложения 2.15 вытекает, что достаточно построить выпуклую минимальную реализацию лишь для скелетов с пюстыо концевыми лнясйнымп участками. Итак, пусть,~' скелет из Ъ'Ло с шестью концевыми линейными участками, получающийся редукпией из классифицирующего скелета У 1-го нли П-го типа. Пусть 1 направляющая единственного линейного участка Ь цз о, являющегося ломаной змеей. Пусть Ь соответствующий й линейный участок скелета я, и пусть,Ь~ и ллз ячейки ветвления, приьпькающио к 1. Пусть 1' построенная в предложении 2.17 минимальная реализация линейного скелета Л' = й О лм О Лз в некоторой трапеции СьС РзР~ = Р, основания которой параллельны ! н лежат па прямых 1~ и 1з. Пустьн как и вьппе, С„Е 1,.
Рассмотрим, для определеннопги, реализацию двоиственцого графа Гп, ячейки Лы Так как Л~ ячейка ветвления скелета,ч', полученного редукциен яз классифипируюшеь о скелета 1-го или П-го типа, к ней примыкает ровно один концевой линейньш участок скелета Я. Обозначим через с ребро Теорема реализации графа Рвы принадлежащее двойственному графу этого концевого .плпейно~ о участка, а через / второе, отличное от е, ребро из 1 ам являющееся г1эаничным ребром двойственного графа паркета Г'. Пусть с' обозначает реализацию ребра е, а ~' реализацию ребра /'. Из геометрии классифппирующих скелетов 1-го и П-го типов легко выводится, что каждая из точек С„.
инпидснтна одному из ребер е' или /'. Буде л, для определенности, предполагать, гго граничные верпплны реализапий е' и /' совпадают с С~ и Сз соответственно. Рассмотрим часть паркета В, которая прпмьпгаст к ячейке дм н не пересекается с паркетом В. Оиа, очевидно, представляет собой лпзъюнктное объединение примыкающего к Дм концевого линейного участка б1~ и пс более чем лестницы Лы разветвляющейся в ячейке ветвления Ьз на два концово~ о линейного участка Яз и Оз. Обозначим через Л~~ лестницу Л~ с присоединенной к ней ячейкой ветвления ххз. Ясно, что Т'~ снова является лестницей. Ори< нтирусм направляющую! паркета Г/ в сторону его концевой ячейки Лы что:ш даст нам ориентацию прямых 1з и 1з.
Рассмотрим отрезок С~ С, и ориснтирусм его от Сз к Сз. Обозначим через о абсолютную величину Угла междУ напРавлспиЯми вектоРа С~ Сз и пРЯмой Рь ПосколькУ СЗ и Сз инцидептны ребрам сети Г, выходящим из одной точки !Птейцера, о лежит в следующих пределах: я/б < о < бп/б. Возгиожны следующие два случая: угол о меньшс н/3 или угол а больше или равен л/3. 1эассмотри л первый случай. Тогда ребро е' перпендикулярно 1ы а ~' составляет с 1з угол в х/б, см. рис. 2.25.
Отсечем от трапепии Р вблизи вершины Сз достаточно малый треугольник СзАВ, А Е С~Сз, В б 1з, глс отрезок 4Л перпендикулярен первому звену оси линейного участка 1,ы Выберем треугольник СзАВ столь малым, чтобы он не содержал граничных вершин графа 1', отли шых от Сз. На рис. 2.26 приведены все возможные случаи расположения треугош,пика СзА В.,'Заметим, что угол Сз треугольника СзАВ равен о, поэтому, по предположению, этот угол меньше чем я/3.
Отсе ~ем от треугольника Сз 4В треугольник СзАГ, выпустив иэ точки А луч АГ под углом л/3 к прямой 1з. Легко видеть, что треугольник ГАВ прямоугольный, и ребро /' пересекает его катет ЛВ по некоторой внутренней точке Х. Теперь мы находимся в условиях предложения 2.!8, что ласт нам возможность реализовать лестницу 1,' в некотором четырехугольнике, полученном отсечением от треугольника ГАВ некоторого треугольника г В!', рис.
2.27. Легко видеть,что в этом случае ребра построенной минимальной сети, ипцндептныс вершина л С' и !',выходят из одной точки 1Птейнера и приходят на стороны угла 1" под прямым углом. Поэтому треугольник ВВ!' остроугольный с углом Г, равным х/3, и, следовательно. его углы 12 и Н больше г/б и меньше я/2. !36 Тсеорема реализации Р А=В Р д=! Р А=! Рис. 2.28: Все возможныс случаи расположения треугольника ВЕГ Рассмотрим второй случай, т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
