Геометрические свойства локально минимальных сетей (1097521), страница 4
Текст из файла (страница 4)
Алгоритм, предложенный Кокейном, состоит в следующем. Пусть П некоторая оболочка Штейнера. Рассмотрим всевозможные пары соседних на дГ точек из М, и для каждой такой пары А, С найдем все хорошие точки В Е ЛХ и рассмотрим соответствующие клинья Иг, порожденные АВС. Из всех построенных клиньев выберем тот клин И'о, у которого угол при вершине В максимальный. Если таких клиньев несколько, то возьмем любой из них. Обозначим через П' множество ХХ 1, И'о, которое, как мы уже знаем, является оболочкой Штейнера для ЛХ., поэтому для Г' можно повторить описанную процедуру, Алгоритм заканчивает работу, когда для построенного на предыдущем шаге множества П ни для какой пары соседних на дХХ точек из М нет хорошей точки из ЛХ. Предложение В.1 (Кокейн) Пусть ХХ 'некоторая оболочка ХПтейнери множестви М. Применим к Г описанный выше алгориепм.
Полученное в результате множество ХХ определено однозначно и является оболочкой Шп~ейнера для ЛХ. Отметим, что в результате описанной процедуры может получиться множество, представляющее собой объединение многоугольников Р„ соединенных между собой некоторыми ломаными Хи (возможно одноточечными). Эти ломаные, очевидно, составлены из ребер абсолютно минимального дерева.
Более того, в этом случае достаточно построить абсолютно минимальные деревья для каждого из множеств ЛХ, = М П Р,. Абсолютно минимъчьное дерево для всего множества ЛХ при этом совпадает с объединением абсолютно минимъчьных деревьев для ЛХ, и ломаных В,ь Подчеркнем, что описанная выше процедура улучшения оболочки Штейнсра не единственна. Например, Хванг, Сонг, Тинг и Ду в ~23) Введение.
предложили способ, позволяющий отрезать от оболочки Штейнера некоторые четырехугольники специального вида. Мы не приводим здесь их результат, отсылая к работе ~23). 2.3 Гексогональная система координат Как было отмечено выше, имеются алгоритмы Мелзака и Хванга, позволяющие находить все абсолютно минимальные сети, затягивающие данное множество ЛХ точек плоскости.
В действительности, эти алгоритмы перебирают все затягивающие ЛХ плоские деревья, степени вершин которых не превосходят 3 (такие деревья называ|отся деревья.ми Штейнера) и для каждого такого дерева Г проверяют, существует ли планарно эквивалентное ему локально минимальное дерево Гьг затягивающее множество Л~Х, такое что ограничение на множество ЛХ планарной эквивалентности, переводящей Г в Г, является тождественным отображением, Если такое Г существует, то алгоритмы строят его в явном виде и вычисляют длину. На заключительной стадии длины всех найденных локально минимальных сетей сравниваются между собой и выбирается локально минимальное дерево наименьшей длины.
Это дерево и является абсолютно минимальным. Геометрическая конструкция, лежащая в основе алгоритма Мелзака, является обобщением построений Торричелли и Симпсона, см, подробности ниже, В процессе работы этого алгоритма дополнительные вершины минимальной сети точки Штейнера, вычисляются как точки пересечения отрезков и окружностей, Сравнительно недавно Кларк ~8), а затем независимо Хванг и Венг ~36), предложили алгебраическую версию алгоритма Мелзака, в которой точки Штейнера находятся как решения линейных уравнений.
Хванг и Вснг использовали в этих целях так называемые гексогональные координаты. Пусть на плоскости фиксированы три прямые Н, 1' и И', пересекающиеся в точке О и разбивающие плоскость на шесть равных утлое. Фиксируем ориентацию каждой из этих прямых так, как показано на рис. 6. Каждой точке Р плоскости 11з поставим в соответствие три числа (и,и,ю), где и алгебраическая величина проекции точки Р на ось ХХ вдоль оси 1', и ачгебраическал величина проекции точки Р на ось 1' вдоль оси И', и, наконец, в алгебраическая величина проекции точки Р на ось И' вдоль оси 1Х.
ь1исла (и,п,~ю) называются енсагвнальными координатами точки Р в системе координат Х)1'И". Иногда гексагональные координаты точки Р обозначаются через (и(Р), и1Р)., ю(Р)). Следующее утверждение очевидно. 2. Абсолютно минимальные сети. н т1 %»' Рис. 6: Гексагональные координаты. Утверждение В.б Для произвольной точки Р плоскости йз выпол- нено следующее соотпношение: и+ о+ ю = О.
Пусть Г локально минимальное бинарное дерево, каждое ребро которого параллельно одной из осей гексагональной системы координат. Отметим, что если отрезок АВ параллелен одной из гексагональных осей (например, оси о'), то соответствующие гексагональные координаты (в данном случае и-координаты) точек А и В совпадают. Отсюда вытекает следующее утверждение. Утверждение В.6 Если ребра локально минимального бинарного дерева Г параллельны соответствующим осям гексагональных координат, 'по координаты всех точек П1тейнера дерева Г являются линейными функц ями координат, то ьек множества ЛХ и вычисляются однозначно. Дааее, напомним, что каждое дерево является двудольным графом.
Последнее означает, что множество вершин дерева можно разбить на два подмножества, называемые долями, так, чтобы каждое ребро дерева соединяло вершины, принадлежащие разным долям. Пусть Г = Ъ~ Н Гз —.— такое разбиение множества Г вершин локально минимального бинарного дерева Г. Утверждение В.7 Пусть на плоскоспш фиксирована гексагональная система координат ПЪ'И', Пусть Г -- локально минимальное бинарное дерево, загаягивающсе множество М, и предположим, что каждое ребро дерева Г параллельно одной из координапьных осей. Тогда, для произвольного разбнени Г = Ъ~ й 1: множества вершин дерева Г на доли, и.неем: [и(Р) + и(Р) + ш(Р)~ — ~ [и(Р) + е(Р) + ю(Р)1 = О.
геььом ремом Введение. 14 Утверждения В.б и В.7 показывают, что гексагонэльные координаты граничных точек множества М., затянутого фиксированным минимальным бинарным деревом, связаны между собой линейным уравнением. Это уравнение называется характеристическим. Отметим, что если рассмотреть дерево другой топологии, то характеристическое уравнение окажется, вообще говоря. другим,так как изменится разбиение множества вершин дерева на доли. С помощью характеристического уравнения удается найти направления робер минимального бинарного дерева данной топологии, затягивакьщего данное множество точек (если такое дерево существует), или,что все равно, найти гексагонвльную систему координат, оси которой параллельны ребрам этого минимального дерева.
'Утверждение В.8 Если сисепема гексагональных координат Гуч11м повернута относительно исходной системы 171'Ис на угол 1о против часовой стрелки, то для произвольной точки Р имеем: где к = з1п(р)/у'3, а 1= сов(1о). Воспользовавшись утверждением В.8, можно записать характеристическое уравнение, которос, очевидно, будет линейным уравнением на й и 1. Поскольку повороты на углы 1о, уо+2я(3 и со+ 4к/3 дают, очевидно, одинаковые, с точностью до обозначения осей, системы координат, а также поскольку имеет место соотношение) + Зкз = 1, можно, найти угол р (если такой существует), удовлетворяющий характеристическому уравнению. Итак, имеет место слсдующсс предложение.
Предложение В.2 11кларк, Хванг, Веиг) Исходя из гексагональных координат точек множества М и топологии бинарного 'дерева Г с границей М, с помо<пью характеристического уравнен я, можно найти направления ребер невырожденного минимального дерева Г с той же границей М (если такое дерево существует). 2.4 Абсолютно минимальные деревья, затягивающие множества специального вида Иногда, если наложить достаточно жесткие ограничения на устройство граничного множества М, удается полностью решить задачу о 2. Абсолютно минимальные сети. поиске абсолютно минимального дерева. В настоящем пункте мы расскажем о некоторых задачах такого типа. Отметим, что большинство рассматриваемых в данном пункте граничных множеств лежит на границе своей выпуклой оболочки. Такие граничные множества мы будем называть еьп»укль ми .
Зигзаги Рассмотрим на плоскости ломаную Хь звенья которой 'поворачивают в разные стороны". Последнее означает, что если фиксировать некоторую ориентацию ломаной Е, и каждой паре последовательных вокторовзвеньев ломаной Х поставить в соответствие знак ориентированного угла от первого звена ко второму,то получится знакопеременная последовательность. Ломаные, обладающие таким свойством, называются зигзагами. Пусть теперь М -"- конечное множество точек плоскости.
Множество ЛХ называется зигзагом, если существует ломаная-зигзаг Хч множество вершин которой совпадает с ЛХ. В этом случае говорят, что Х, иараметризует зигзаг М. Пусть ЛХ = ХЛХД»' » некоторый зигзаг, параметризованный ориентированной ломаной-зигзагом Х. Предположим, что точки из М занумерованы последовательно в соответствии с ориентацией Х. Зигзаг ЛХ называется регулярным, если существует такая его парамстризация Х,, что последовательные углы ЛХ»ЛХ»+»Мгьг ломанои Х, одинаковы по величине.
Величина этого угла называется в этом случае углом зигзага ЛХ в данной параметризации. Зигзаг ЛХ называется вьгауклым, если множество ЛХ лежит на границе своей выпуклой оболочки. Зигзаг М называется нормальным, если выполнены следующие неравенства: РЛХ,ЛХ., »й <~',ЛХ»ЛХ, Д, У «Л — З. ~~ЛХьь»М,,з~~ < ~~ЛХ»ЛХгез~~~, 2 <» < Л вЂ” 2. Непосредственно из определений вытекает следующее несложное утверждение. 'Конечно, подмножество плоскости, состоящее из конечного числа п точек, и ) 2, не является выпуклым и стандартном смысле этого слова.
Множества, лежащие на границе сноей выпуклой оболочки обьгщо называют экетрелзольяыми. Однако, а данном кон гексте для экстремальных граничных множеств традиционно используется тсрмна "выпуклое граничное множес гно". Мы не будем отступать от общепринятой терминологии. Введение. 16 Лстверждеиие В.9 Пусть ЛХ "- некоторый зигзаг.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
