Классификация локально минимальных плоских сетей с выпуклыми границами (1097579), страница 4
Текст из файла (страница 4)
принадлежат ЛХ. В отличие от локальной структуры минимальных сетей, которая полностью описана, про глобальнос устройство известно далеко не все. Конечно, ясно, что каждая абсолютно минимальная сеть является деревом, степени вершин которого не болыпе 3. В частности, абсолютно минимальное дерево содержит не более и — 2 вершин, не лежащих в граничном множестве ЛХ (напомним, что чсрсз и мы обозначили количество точек в ЛХ). Зти дополпительныс вершины называются точкаяи ХХХтейнери. Мы уже отмечали, что задача построения абсолютно минимального дерева Хр-полная, я этот факт является одной из могивапий, обосновывающих актуальность основной задачи настоящей диссертации: научиться по геометрии множества ЛХ понимать, какие топологии нс мо~ ут заведомо встречаться в абсолютно минимальных сетях, затягивающих ЛХ.
Иными словами, требуется исследовать дополнительные свойства абсолютно минимальных сетей и связь этих свойств с геометрией тряпицы ЛХ. Одно из таких свойств формулируется в терминах так называемой оболочки Штейнера. 31сгко показать, что сели известно расположение точек Штгйнера из абсолютно минимального дерева, то все абсолютно минимальные деревья с,чапным расположением точек !1!тейыера известны и являются всевозможными минимальными остовными деревьями, затягивающими объединение множества ЛХ с множеством всех этих точек 1!!теинера. Поэтому полезно выделить подмнохсество плоскости, за пределы когорого точки 1лтейнера попасть не могут.
Лбсолотно минимальные сети 2.1 Оболочки Штейнера Приводимые ниже результаты можно найти в обзоре [22], а также в ста- тье ,"6). Опрод< жэние. Множество Я!(Л|) С !Рз называется оболочкой Штейнера лножсстоа М, если каждое абсолютно минимальное дерево, затягиваюшсс Л|, содержится в НН(Л|). Х!сво, что )ем мевыпую по включению оболочку П1теивера вам удастся найти, тем более сильные ограничения на расположение точек !!1тсйисра мы получим. Т!риведем веско,п,ко характерных результатов ва зту чему.
Пусть à — абсолютно минимачьпос дерево, затягивающее множество Л1. Утверждение 1 (Свойство бесконечного клина) Пусть УИ енутренность некопь рого угла ееличины не,пените чем 2к1:1. Предположи,н, чппо И' нс содсржшп точек из Л|. Тогда. И' нс содержит точек Шппйнера дерева Г. Виутрсияость угла Иг часто называют бссконечныж клина.н, Следствие. 1 Выпуклая оболочка множеспша Л1 яелж тся одной из обо- лочек Шп~сйнера длл Л|. Пусть Г, как и вьппс, обозна тает абсолютно минимальиое дерево, затягивающее коне шое множество Л| точек плоскости. Рассмотрим некоторый треугольник ЛВС, утоп В которого нс мсиьшс 2к/3.
Обозначим через Иг множество, полученное ич ЛВС выбрасывание л сторон !В и ВС, прилежащих к углу В. Миожесгво И' будем называть !огриниченныл) клина.ч, порожденным ЛВС. Утверждение 2 Пусть клин И', порожденный АВС, нс содержит пьочек лножестео ЛХ, а отрезок ЛС лежит на границе некоторой оболочки |Птейнера НН(Л1). Тогда И' не содержит точек!Птейнера абсолютно минимального дерсоа Г, зопглгиеоющсго ЛХ. Приведем здесь еще одно утверждение, позволяющее умевыпать оболочку Штсйиера. Лункой 1., соответствующей отрезку АВ, назовем пересечение двух открытых кругов радиуса АВ с центрами в А и В соответственно.
Утверждение 3 (Свойство лунки) Пугин Г абсолюепно яинилтт— нос дереоо, затлгиоаюилсс .нножсстоо ЛХ, и АВ произьольное ребро из !'. 1'огда лунка |о соотестстпуюи!ал ЛВ, не содсржшп, горшин дсрсеа Г. Лбсошотно минимальные сети Известно несколько способов пероходить от однои оболочки Штайнера к другой, меньшей. Иы приведем здесь один из них, предложенный Кокеином [бз). Пусть Г некоторый ъшогоугольнпк па плоскости, являющийся оболочкой Штейнсра множества ЛХ, а дГ его граница. Пару точек И и С из ЛХ назовем соседними на дГ, если отрезок з!С лежит на дГ, и на интервале АС неч точек из ЛХ. Пусть А и С пара соседшлх на с)Г точек нз М. Точку В из ЛХ назовем хороишб дяя А и С, если угол В треуь ольнвка А ВС не меньше 2к/3, и оь раничснный клин И', пора кдснный ЛВС, нс содержит точек из М.
Утверждение 4 В сдеяанньи: тяте предьптоясениях, .нпоакество Г', позупттое из Г выбрасываппен оераниченпого каипа И', является обола о кои' Игпелзнера дяя М. Ллгоритм, предлозкенный Кокейном, состоит в следующем. Пусть Г некоторая оболочка Штейнсра. Рассмотрим вссвозможныс пары соседних на дГ точек из ЛХ, и для каждой такой пары И, С найдем все хорошие точки В б М и рассмотрим соответствующие клинья И', порожденяые АВС. Из всех построенных клиньев выберем тот клин И'з, у которве о угол при вершине В максимальный. Если таких клиньев несколько, то возьмем :пооои из них. Обозначим через 11' мнозкество Г ~ И'з. Б силу леммы 1.1, множсспзо Г является оболочкой 1Птсйнера для М, позтому лля Г можно понто!пзть описанную процедуру. Лзщоритм заканчивает работу, когда для построенного на предыдущем шаз с множества Г нн для какой пары соседних на дГ точек из ЛХ нет хорошей точки из ЛХ.
Предложение 2 (Коксйн) 11усть Г некоторая обола ~ка В1тсйнеро .инолит;тва М. 11ри,пени.я к Г описанный вьшт аягоритж. Полученное в результате .апожество Г определено однознаяно и явяяетпя обоза ~кой П1теь1пера дяя М. Отметим, по в результате описанной процедуры может получиться мнозкес пю, представляклцее собой обьединение многоугольников Р„сосдпнснных между собой некоторыми ломаными Хп [возможно одногочсчшлми). Эти ломаные, очевидно, являются ребрами абсолютно минималь— ноь о лсрсва. Более того, в атом случае достаточно построить абсолютно минимальное дерево для каждого из множеств ЛХ, = М О Р,. Абсолютно минимальное дерево для всеь о множества ЛХ при атом совпадает с объединением абсолютно минимальных деревьев для ЛХ, и ломаных Ха. !1одчсркнсм, что описанная выше процедура улу ппения обола пси 1!! тейнера пе единственна.
Папример, Хванг, Сонг, '! инг и Пу в [1!)) предложили способ, позволяющий отрезать от оболочки!Птсинера некоторые четырехугольники специального вида. Иы нс приводим здесь их результат, отсылая к работе [19). Дбсошотно минимальные сети К Рпс. 8: Гсксагональныс координаты 2.2 Гексагональная система координат Как было отмечено выше, имеются алгоритмы УГслзака и Хванга, позволяющие пахолить всс абсолеотно ълпцимальныс сети, затягивакипис данное мноллество М точек плоскости. В действительности, зти алгоритмы перебирают все затягивающие М п.юскив деревья, степени вершин которых нс превосходят 3 [такпс деревья называются дерь вьлли. Шеееейнера) и для каждого такого дерева !' проверяют, существует ли плапарно эквивалентное ему локально минимальное дерево Г, затягивающес множество М, какое что ограничение иа множество М плацарвой эквивалееггности, переводящей Г в Гт, является тождественным отображением.
Если такое Гт существует, то аш оритмы строят его в явном виде и вычис.ляют длину. НВ закл1О 1и'гол! нОЙ г'гадии,ллины всех е1ВЙденн11Х лОкале е1О мипимальных сетей сравниваются межлу собой и выбирается локьльио минимальное дерево паимецьплей 1!Лпиы. Это дерево и,является абсолютно минимальным. Сравнительно недавно Кларк [5], а зате л независимо Хваелг и Вснг [25), предложили алгебраическую версию алгоритма Мслзака, Хванл и Венл использовали в этих целях так называемые гсксагональныс координаты.
Иусть ца плоскости фиксированы три прямые !з', И и И', пересекающиеся в точке О и разбивающие плоскость на шесть равных углов. Фиксируем ориентацию каекдой из этих прямых так, как показано на рис. 8. Каждой точке Р плоскости кз поставим в соответствие три числа [и, и, и:), где и а'и сбршлч окая величипа проекции точки Р па ось ГР вдоль оси И, о алгебраическая величина проекции точки Р на ось И вдоль оси И, и, наконец, щ алгебраическая величина проекции точки Р на ось И' вдоль оси Гг. Числа (и, и, ео) нззьлваютгя етксагопальны„,яи коордпнаталт точки Р в системе координат !У!ЕИг. Иногда гсксагональныс коор,дпнаты точки Р обозначаются через [и(Р), и[Р), т[Р)). Сле,дулопесе утверждение очевидно.
Утверждение Ь у)лл произвольной точки Р плоскотпи Е аьтолнено сеЕе- дрттв соотношение: и+ и + и; = О. Лбсошотно минимальные сети Пусть Г локально минимальное бинарное дерево, каждое ребро которого парзллеш,но одной нз осей гексагональяой системы координат. Отметим, что если отрезок АВ параллелен одной из гексагональных осей (например, оси В), то соответствующие гексагональныс координаты (в данном случае т) точек Л и В совпадают. Отсюда вытекает слсдующсс утверждение. 'Утверждение 6 Есяи ребра локально мини польного бинарного дерева Г пираллельны соотьетствуюиьим осл.и гексогональных координснщ ьпо координаты оссх точек Вйпейнсра дерева 1' являютсл линтшыми функцияни координат, точек множсютва ЛХ и вычисляютсл однозначно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
