Классификация локально минимальных плоских сетей с выпуклыми границами (1097579), страница 37
Текст из файла (страница 37)
Далее, очевидно, второе вектор-звено ручейка Ьг(А, ЕХо) совпадает с ~, 6з,. Аналогично для ручейка Ьг(А, Ли). 1!оэто лу, ь Л(11) = А+ ~~' 6, = А+~~',6зл-~ + ~ 6эу = 0(Л)+~~' 6ъ = Л(Яо). ю=1 2 3 1 Аьгалогичпо для Лн. Доказательство закончено. Обозначим через Фо и Фн допустимые углы, содержащие дожди, полученные расширением дождей Ло и Лн на множества эХо и АХн соответственно.
Определение. Множество АХо = (А, 0(Ф), В(Ф)) назовем нечстнььн Ф-рсдуцироеанньья, а множество .Ин = (А, Л(Ф), Л(Ф)) четным Ф- рсдииироьинным множествами, полученными пз АХ. Змеи на произвольном множествс Следствие 3.2 Харвктерцстическоя дуга О(Ф) для мнолссства М, соотвсгпстьуютоя допусти ноцц углу Ф, содсржеппся в хороктсристичсскит дугах 11(Фо) и ЦФн) нс- штного и четного Ф-редуцированных множеспгв Мо и Мн. Следствие 3.3 11усть М' = ~ьЛ, Мы Мз,..., ЛХ,Х ночольный о~врезок множество М. Хогдо1-оя хороктерцстическая с)уга ь1„(Ф). соответствую щоя множсствуЛХ, содержится в характеристической дуге множество ЛХ', соогпвсепсгнвцхнцей тому допусгпицому углу, в которо.н лежит Ф. 11олее того, пхый характеристический треугольник совппдоет с елоьны я характсрисесгическил~ треугольником для множсстьо ЛХ'. 2.4 Вполне характеристическая дуга Используя результаты предыдущее о пункта, можно предложить следующий алгоритм проверки того, ложно ли данное множество ЛХ точек плоскости затянуть змеей, выпущенной из точки А Е М.
Сначала проясняется, принадлежит ли точка А границе выпуклой оболочки мнолссства ЛХ. Если это ве так, то змекь выпустеггь нельзя. В противном случае, рассматриваются все А-допустимыс углы, для каждого из них строится своя характеристическая дуга и провсрястсн, лежит лп конечная точка мнохсества ЛХ на этой дуге, т.е.
проверяется, является ли данный угол В-допустимым. Если среди лножества всех Л-допустимых углов нет ни одного и-допустимого угла, то змею выпустить нельзя. В противном случае, рассматривается каждый В-допустимый угол. Если соответствующая ему характеристическая,цуга невырождена, то существует единственный дождь Я из этого угла, такой что Б(ХХ) совпадает с коне евой точкой множества М. Отот,юзкдь может быть легко построен, а именно, конечная прямая этого дождя совпадает с касательной к окружности, описанной вокруг главного характеристического треугольника, проведенной чсрсз консчную точку множества ЛХ. Отметим, что зта касательная параллельна противоположной стороне ~ ванного характеристического треугольника.
Если же характеристическая дуга выроледсна, то придется рассматривать все дожди нз допустимого угла. Осталось проверить, существует ли среди выбранных дождей такой, для которое о це крайние то ~ки множества ЛХ лежат на отростках порожденной этим дождем бесконечной змеи, выпущенной из Л. Если такой дождь найдется, то искомая минимальная змея получается ограничением построенной бесконс шой змеи.
В противном случае, змею выпустить нельзя. 11аличие выролсдеш|о1 о случая, а также некоторые технические соображения, приводят к необходимости более детального исследования последнее о шага этого алгоритма. В настоящем пункте мы сформулируем критерий сущсствовщеия минимальной змеи, выпущенной из точки Л, в терминах Змси на произвольном ыножествс 153 так называемой вполне характеристической дуги, являющейся ограничением характеристической дуги.
Пусть Н| |М;Н| |тый характеристический трсугольник. Его вершину Н, назовем главной. Пусть,5; окрулсность,описанная вокруг трс| угольника Н| |М|Нь Открытую ду|у окружности Н|, лсжашую между Н, | и М„и нс содержащую главной вершины Н„, пазоввы |-ой г званой дугой. Отметим, что если треугольник И, |М,Н; вырождгн, то, по опрсдслснию, |-ая главная дуга пуста.
Отметим, что |-ая главная дуга и |-ая характеристическая дуга лс|кат на одной окружности су,'. Определение. Псрсссчспис |-ой главной дуги и |-ой характеристической дуги пазовом главной чисп|ьн!-ой лврантврнстснсвской дуги и обопичим через д|(Ф]. Пусть гб паркст-зыся, и ХХ нгкоторгл его минимальная реализации на множестве М, выпущспиая из некоторой вершины А б М. Рассмотриы дождь Л', соотвстствуюший У.-, и расширим гго до дождя Л, добавив и' к Л' прямую, проходящую через отличную от 4 концевую вершину змеи гХ-. Пуска Ф допустимый угол для множества М, содержащий расширенно Л дождя Л на М.
Обозна||си через х1|,..., А„последовательные вершины ориентированного от А ручейка Ьг(А, Л). Предложении 3.2 ХХ сдв.лвт|ыл вьш|в првдпвлваисппял, ил|в|от .ивтвв следу|сисис свотвотснилс 4; б с!с(Ф), | = 1,..., и — !. Доказательство. Прюкдс всего, от истин, что если какой-либо характеристический треугольник, отличный от главного, вырождается, то соответствующая точка из ЛХ совпадает с точкой 1Птсйпсра бесконечной змеи, порожденной шобым дождем пз рассматриваемого допустимого угла. П этом случае миниыальную змею выпустить нельзя. Следовательно, все характеристические треугольники, за исключением, быть может, главного, нввырождвны. Доказательство прсдлолссния провслсм по индукции.
Пусты = 1. Так как угол Ал1| М| равсп 2я/3, то орисптированпый угол ысжду направлснисм т дождя Л и всктороы АЛХ| в базисс (сс(Л), т) лсжит в прсдслах между — к/3 и О. Напомним, что Н | получается из М| поворотом вокруг А на угол величины к/3. Поэтому ориснтированный угол между т и всктороы АН| большс нуля и мспьшс к/3. Следовательно, точка Н| лежит в той же полуплоскости относительно прямой г|, что и точка А. Более того, из равгяства 2н/;1 угла 44| ЛХ| и щплнадлвжности точки А| окружности сХ', описанной вокруг треугольника АМ| Н|, вытекает, что А| обязана попасть на ту из двух дуг, стянутых хордой АЛХы которая по величине равна 2к/3, т.г.
па 1-ую главную Ау| у. Поэтому, по определению, .4| б с!|1Ф). Зьтеи на произвольном множествс 156 Пусть т = 2. Так как угол 11тАзМз равен 2г/Ъ, то ориентированный угол между направлением т дождя Я и вектором 11зМз в базисе 1тт(Н), ш) лежит в пределах между — 2тт/3 и — тт. Напомним, что Вз получается из зМз поворотом вокруг Н~ на угол величины — г/3.
Позтому ориентированный утоп между т и вектором НтПз меньше — л и больше — 1к/Ъ. Следовательно, точка Уз лежит в той же полуплоскостн относительно прямой тз, что н точка Ны а. значит. в той же полуплоскости, что и точка А. Более то~ о, из равенства 2я/3 угла НтАзМз и принадлежности точки Аа окружности Вз, описанной вокруг трсут ольника НтМ Нз, вытекает, что 1 А обязана попасть на ту и,з двух дуг, стянутых хордой Л1М, которая по величине равна 2 т/3, т.с. на 2-ую главную дугу.
!! озтому, по опрс велению, Аз Е дз(Ф). Предположим, что для всех т < в ( и — 1 доказано, что Ат Е дт(Ф), и что точка Н, находится относительно прямой г, в той зттс полуплоскости, что и то пса А. '!'огда, дословно повторив рассуждения для т = 2, если 1. чстно, и для т' = 1, если й нечетко, получим, что у1л Е дь(Ф). Предложение доказано. Рассмотрим множество тех дождей из Ф, у которых каждая точка А, лежит на своей дт(Ф), т = 1,..., п — 1. Соотвстствуюшсе подмножество допустимого угла Ф назовем базой спалит.
характеристической дуги. /!ля каждого дождя Н пз базы вполне характеристической дуч и рассмотрим соответствующую ему точку В(В) на характеристической пут с РтФ). Определение. Построенное только что подмножество характеристической дуги Р(Ф) назовем вполне харакпгерпстпчсскай дугой и обозначим через Рн(Ф).
!'ак как казкдая из т-ых главных дуг и т-ых характеристических дуг связна и открыта, то вполне характеристическая дуга илн пуста, или представляет собой связну ю открытукз дугу окружности Вт !Ф). Отметим также, что вполне ха!эактсристпчсская дут а может быть пуста, в то время как сс база нет. Из предложения 3.2 непосредственно вытекает. Следствие 3.4 В прсдпололссниях пред.,тахстнттл д21з, база вполне характпсрттттттзчетзквт! дуги 1дтт(Ф) не пуста. Валье тпагв, если главный харакпперишпический треугольник нсвыражден, тт1а вттвлне характттсристичвскал дуга Ртт(Ф) также нс пуспшз и содержит та тку В(Ф) = Ап. Теперь все готово лля того, чтобы сформулировать основной результат пастоящсго параграфа. Предложение 3.3 (Кузиторий сущтзствования минимальной змеи) 1'.анвчнае множестава ЛХ точек а.таскоспш малсно заталнуть минииатьной змеей, выпуитспнвй из то тки А е Л1, тогда и только тогда, когда Змеи на произвольном множестве 157 среди Л-допустимых углов существует такой Н-допутпижый уеол Ф, т|о база вполне, харакп|еристическо|! дуги не пуста.
При зтож, если главный характеристиче|пеиб п|реугольник невырожден, то конечная точка Н(Ф) .т|ожества ЛХ относип|ельно Ф принадлежи|и, вполне харатнерис|пической дусе ХУ'(Ф). Доказательство. Прямое утверждение содержится в предложении 3.2. Докажем обратное утверждение. Пуст|и как всегда, Л начальная точка ъп|ожества ЛХ по отношению к некоторому проходя|нему через М регулярному ориентированному дождя| Н с выбранных| направлением распространения си(Н).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
