Классификация локально минимальных плоских сетей с выпуклыми границами (1097579), страница 31
Текст из файла (страница 31)
10.3 Реализация ломаной змеи и лестницы Пель настоящего раздела построить ми|п1ъзальную реализацию произвольного линейного деревянного скелета, являющегося нс более чем ломаной змеей, в некоторой трапеции специального вида. Напомним, сто две 'Георема реализации эквивалентных минимальных сети называются параллельпыжи, если после произвольнои ориентации параметризуюшего пх графа соответствующие !зебра этих сетей являются сонаправлснными векторами. Пусть Г линейный деревянный скелет (участок), Яр! его осьь уи ВРЬ ( 2, и 1 некоторая сто направляюшая.
Предложение 2.17 Сутсстоутп жиниистьная сеть Г, параллельная доойстаспножу графу Гл паркета 1, такая что се граничные аеригины располозксны на границе некоторой трапеции Р с параллельны.пи ! оспоаапия,пи, причс.,и каэкдая агритна трапеции Р является граничной асриитой сети Г. Доказательство. Прнентпруем ось Яр 7., и пусть направляющая ориентирована так, что проекция каждого звена оси Яр 1 на ! положительна. Папомним, что каждый линейный скелет !участок) А представляется в виде объединения последовательно идущих змей га разных направлений.
Разобьем множттво змей Х, на два класса. К первому из них отнесем эмси Л,, оси которых параллельны направлякпцей 1, а ко второму все осгальные змеи Уь Заметим, что оба этих класса упорядочены в соотвстствиц с порядком во множестве (Х,). Для каждан змеи У, выделим примыкающие к пей ячейки паркета 1,. Ясно, что эти ячейки содержатся в змеях Л, и могут, вообще говоря, совпадать для разных У).
Пусть (!х;) множество выделенных ячеек, упорядоченных в соответствии с порядком, заданным на ячейках паркета !. оряептапиеи направляющей 1. Пусть П некоторая полоса, параллельная 1, ограниченная прямыми 1~ и 1з. Разобьем некоторую часть этой полосы на последовательно идущие прямоугольники Пб диагонали которых перпендикулярны соответствующим направляющим паркета плоскости, отличным от 1. Построим столько таких пряхсоугольников, сколько имеется змей Уо Ясно, что выбранная ориентация направляющей ! задает, плюс ко всему, естес пзенный порядок на множестве прямоугольников П;, поэтому возникает взаимно однозначное соответствие между (У) и !П,), сохранякяцее порядок. В каждом прямоугольнике П, проведем ту дию оиальь которан перпендикулярна оси соответствующей ему змеи У).
При 'этом прямоугольник разбивается на два треугольника. Подправим теперь полученное множество треугольников. Пусть 'Г и 7ч два последовательных треугольника, первый из которых содержится в Пь а второй в Пь.~. Пусть в Г между змеями Уь и У;г.~ расположена змея Х . Если змея Х состоит ровно из одной ячейки, склеим треугольники '!' и 7ч в один по их общей стороне. Кро лс того, если начальная !коне шая) змея из й не параллельна направляющей 1, то выкинем начальный !конечный) треугольник.
Рассмотрим перестроенное так множество треугольников, последовательныс элементы которого будем обозначать через 7', .'1егко видеть, что между множеством (Ь,) выбранных 120 Тгеорема реализации 27 Рис. 2.22: Минимальная реализация линейного деревянного скслста выше ячеек из А и множеством треугольников Т; существует единственное взаимно однозначное соответствие, сохраняющее порядок. Для удобства, стороны треугольников '1';, нс параллельные 1, назовем бояоаыжп. На ъшожсствс боковых сторон таэгже имеется естественный порядок. Множество так упорядочешплх боковых сторон обозначим через 1а,!.
Рассмотрим боковую сторону с трсутольника Ть Каждый параллелограмм, построенный снаруэки треугольника 7;, так что две его стороны лежат на границе полосы П, а третья совпадает с е, шэ.эовем ээрп,яьэкаээШпж. Стороны примыкающего параллелограмма, параллельные е, также будем называть боковглжи. Искомая минимальная реализация строится так (см. рис. 2.22). Разобьем Е на участки трех типов: змеи Уо постросэнэые вылив, ячейки Ь„ примыкающие к ним, и змеи Х,, из которых выброшены ячейки Ь,. Отметим, что:элементы третьего типа ээоэ ут быть пусты. Послсдовательныс злсменты только что построенного разбиения будем обозначать через Уь Будем последовательно реализовывать последовательные злемепты У, так.
Элемент Уэ является, очевидно, змеей. 1эассмотрим примыкающий к нервов боковои стороне аэ параллелограмм, и пусть еэ другая боко- ваЯ стоРона этого па1эаллслогРамма. ФиксиРУем на стоРоне сэ пРоизвольную внутреннюю точку Еь Выберем параллелограмм столь "узким" (т.е. с достаточно близкими боковыми сторонами~, чтобы граничные лучи характеристического конуса ь(!уэ, 1!э), где У, дождь, параллельный еэ и отделяющий еэ от аэ, пересекали аэ по внутренним точкам.
'1огла, в силу следствия 2.11, в выбранном примьэкаюшсм параллелограмме существует такая минимальная реализация змеи Уы удовлетворяющая условиям предложения, что одна сс концевая вершина совпадает с Еь а вторая с некоторой точкой Лэ, лежащей внутри аэ. Элемент Уэ, очевидно, является ячейкой Лэ. Ностроим в треугольнике Тэ минимальную сеть соответствующего направления, эквивалентную двойственному графу ячейки Лэ так, чтобы одной из ее грани шых вершин являлась Аы а друэ ие две лежали на внутренностях дээух других сторон 'Георема реализации треугольника 'Гь отличных от о~.
Легко видеть, что этого всегда можно добиться, при произвольном !эасцолсээкепии точки Аэ внутри стороны оь Обозначим через Аз граничную вершину только что построс;иной минимальной сети, лежащую внутри стороны оз. Если 11з является ячсикои сьз, то аналогично реализуем двонственныи граф иэ Лз в треугольнике уз. В противном случае, рассмотрим достаточно узкий примыкающий к оз параллелограмм и, .так же, как и выше, реализуем в нем змею 11з, начинающуюся в точке Аз и приходящую в некоторую внутреннюю точку Ез второй боковой стороны ез этого параллелограмма.
Сдвинем обьелинение треугольников 'э"„1 > 2, оставив па месте треугольник 1) . так, чтобы образ )эз ооковой стороны оз треугольника 'Гз совместился с ез. Образы счтэ!эон об 1 > 3, будем по-щэе кнсму обозначать через оь Продоллсим описанный только что процесс до тех пор, пока нс будут реализованы все .элементы Н,. В результате получим выпуклую мипимальнукэ реализацию скелета (участка) 1 в трапеции Р', явл»копей< я обэьединснием смещенных треугольников 1', и примыкакэших к ним параллелограммов. Продолжим теперь тс ь раничныс рссэра построенной реализации, которые вышли на боковые стороны трапеции Р', до пересечения с прямыми 1,. '!ак перестроенную гоинимальнуэо реализацию обозначим через ! . Отметим, что вес граничные вершины соти Г лежат на прямых 1ь ка кдую из которых ориентирусм в направлении прямой 1..
Обозначим через С, первую граничную вершину на прямой 1,, а через 1), последнюю. Тогда искомая трапеция Р это С~СзРзРь Локазателытво предложения закончено. 10.4 Реализация лестницы в усеченном треугольнике В настояпюм разделе будет построена минимальная рсализапия линейного скелета )участка), являнэщсгося не более чем лестницей, в некотором усеченном треугольнике специального вида. Пусп, 1, линейшлй деревянный скелет (участок), Вр). его ось, !к бр й < ), и пусть 1э и 1 лве направляющие для Е. Ориентируем ось Вр Е.
Выберем на 1э и 1з ориентации, такие что проекция каждоь о звена оси Вр 1. на прямую 1, была бы отрицателыьа. Рассмотрим на плоскости ш ол Е, стороны которого представляют собой лу 1и тэ и тз, сонаправлснныс с 1э и 1з соответственно. Пусть РЕЕ прямоугольный треугольник, гипотенуза ГЕ и меньший катет РГ которого лежат на сторонах угла Г, а больший катет 1ГЕ перпендикулярен первому звену оси Вр 1.
Пусть Л' произвольная внутренняя точка катета РЕ. Предложение 2.18 Суи!есэнвусэп,жвиволснтноя с)войсоэвснножу графу !'ь поркети 1. лшнинальная сеть Г, токия чинэ ее грониусэ о)эвнодлелсого границе некоторого вынуклогсэ нетырекуголюшко, оолучонэо!егося ог гнрэеуголь- '!гарема реализации Р в. ,,'' тз Г Е Рис. 2.23: Босконечная цослсдовагельность прямоугольных треугольников ника УЕЕ отсечением вшпроугодьпаго трейга„ленина с вершинои' Е. При эллам, жипижальныс сети Г и Гь параллельны; первой кцнисввй вершине двойственного графа Гь соответствует то та .Х; веригины четырехугольника, от,.личнын от В и Е, лнллкцпся граьшчнылш нерлиипажи сеяли Г.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
