Геометрические свойства локально минимальных сетей (1097521), страница 5
Текст из файла (страница 5)
Если зигзаг ЛХ вьтуклый, то отрезок ЛХ~ Л1ь пересекает каждый отрезок Л1,.М,ьы Если зигзаг ЛХ нормальный, то угол М,ЛХ,.ь,ЛХ,сз не меньше чем к/3. Рассмотрим регулярный выпуклый зигзаг М, и пусть о -- угол зигзага ЛХ, а Х парамстризуюшая ЛХ ломаная. Обозначим через Ь; невырожденные треугольники, ограниченные ломаной Х, и отрезком ЛАЛХы см. рис 7. Построим в каждом треугольнике А; абсолютно минимальное дерево Т„затягивающее вершины треугольника Ьп и обозначим через Т дерево, совпадающее с объединением ОТ; деревьев 7",. Положим — ьЛХзз — еМзаь' н уг — 'ь™гМзт' е |! ° Тогда имеет место следующий результат, доказанный Ду, Хвангом и Венгом ~20).
гд — 1 Рис. 7; Абсолютно минимальная сеть, затягивающая зигзаг. Предложение В.З (Ду, Хваиг, Венг) Если М регулярный выпуклый нормальный зигзаг с углом о (по отношенню к некоторой фиксированной ешрвметрнзациа), то пошороенное выиге дерево Т является абсолютно минимальным деревом, затягивающим ЛХ, Его длина имеет, вид: (2,'х ) +12,'у) — 2(2,'х )(~ у ) сог(к/3+о) при к/3 < о < 2к/3, прн 2к/3 < о < к. 2,'х, + 2,'У,, Из предложения В.З вытекает, что при к/3 < и < 2к/3 абсолютно минимальное дерево, затягивакьщее регуллрный выпуклый зигзаг с углом о, содержит точки Штейнера, а при 2к/3 < о < к --- не содержит. Последнее означает, что абсолютно минимаяьное дерево в этом случае совпадает с минимальным остовным деревом.
2. Абсолютно минимальные сети. 17 Точки на окружности Другой класс граничных множеств, для которого удается найти абсолютно минимальное дерево, это точки, расположенные на окружности достаточно плотно. Оказывается, в этом случае абсолютно минимальное дерево является минимальным остовным деревом для своих граничных точек. Пусть М = (М,;) --. конечное множество точек плоскости, лежащих на окружности единичного радиуса.
Положим р = ъгЗ/2, и к = 1— (1 — р)я,1р = 0,51399.... Тогда имеет место следующий результат, полученный Ду, Хвангогл и Чае [19). Предложение В.4 (Ду, Хванг, хааа) Если длины всех шпорон многоугольника М, кроме, быть может, одной, меньше, чем к, то абсолютно минимальное дерево для множества М представляет собой объединение всех сторон этого многоугольника, за исключением самой длинной.
Усиление этого результата получено в работе [73) Рубинштейна и Томаса. А именно, имеет место следующий результат. Предложение В.б (Рубиншттйн, Томас) Пусть М = (ЛХ;) — конечное множество точек плоскости, лежащих на окружноспш радиуса г. Если не более одной стороны многоугольника ЛХ имеет строго больигунь чем г длину, то абсолюьвно мьтимальное дерево для множества ЛХ предстоял ет собой объединение всех сторон этого многоугольника, за исключением самой длинной, "Достаточно плотные" выпуклые многоугольники Следующий результат полу.чен Рубинштейном, Томасом и 1(еле [86) н яаяяется обобщением предыдущего.
Авторы статьи [86) описывают некоторый класс выпуклых многоугольников, для которых абсолютно минимальная сеть снова совпадает с множеством сторон многоугольника, за исключением самой длинной. Вершины этих многоугольников по-прежнему расположены "достаточно плотно", но у.же не обязательно лежат на окружности. Пусть ЛХ = (ЛХв,, .., ЛХь. д) последовательные вершины некоторого строго выпуклого многоугольника, который будем обозначать той же буквой ЛХ. Для удобства предположим, что индексы 1 в ЛХ, являются элементами группы ь„.
Для любых трех последовательных точек ЛХь м ЛХ; и ЛХ,ъ~ обозначим через г; и О; радиус и центр окружности, описанной вокруг треугольника ЛХ,, ЛХнРХьь,. Наименьшее из г, число г называется радиусом максимальной кривизны многоугольника М. Введение. 18 Мы говорим, что четыре последовательных вершины ЛХл и ЛХо ЛХ;, 1 и М, г совместимы, если центры О,; и Очл окружностей, описанных вокруг соответствуюлпих треугольников, лежат с той жс стороны относит прямой (ЛХо ЛХл г), что и все остальные точки М.. Предложение В.б (Томас, Рубинштейн, Коле) Пусть г . — радиус максимальной кривизны выпуклого многоугольника И, и пусть все последовательные четверки точек из М совместимы. Если не более одной, стороны многоугольника ЛХ длиннее чем г, то абсолютно минимальна сеть, зат гиваютал М, состоит из всех сторон многоугольника ЛХ, за исключением самой длинной.
Вершины квадратной решетки В работах ~3) 16) австраяийских математиков под руководством Рубинштейна выполнен цикл исследований, описывающих различные свойства абсолютно минимальных сетей, затягивающих конечное множество М, состоящее из вершин стандартной квадратной решетки. Эти работы развивают результаты, полученные в ~10) и [11), в первой из которых были исследованы абсолютно минимальные сети, затягивающие так называемые лестницы, т.е. все вершины с координатами (тзп), где 1 < т < то, и = 1,2, а во второй высказана гипотеза о том, как устроены абсолютно минимальные деревья для решетки размера 2ь х 2л, т.е. для решетки, составленной из всех вершин вида (т, и), где 1 < т < 2" и 1 < и < 2ь. Л именно, Чанг, Гарднер и Грехем предположили, что в этом симметричном случае абсолютно минимальная сеть также имеет симметричную структуру и составлена из одинаковых 'элементарных кирпичей", совпадающих с абсолютно минимальным деревом, затягивающим вершины единичного квадрата.
Эта, гипотеза была доказана в ~4). В последующих работах Бразил, Рубинштейн и Томас показали, что уже в случае решеток разлгера 2" х 2', к ф. Е соответствующие абсолютно минимальные деревья содержат более сложные блоки, см. рис. 8. Так как эти результаты австралийской школы требуют для своей формулировки введения многих новых понятий, описывающих структуру абсолютно минимальных сетей, мы не будслг приводить их здесь, а ограничимся сделаннылли ссылками и некоторылги примерами, приведенными на рис. 8.
2. Абсолютно минимальные сети. Рис. 8: Примеры абсолютно минималы~ых сетей, затягивающих вер- шины, лежащие на квадратной решетке. 2.5 Минимальные остовные деревья как приближенные решения проблемы Штейнера Рассмотрим все сети, затягивающие множество ЛХ, такие что каждая вершина сети принадлежит ЛХ. Сеть наименьшей длины среди этого семейс~ва се~ей называется минимальным остоенын деревом. Ясно, что полученная сеть, вообще говоря, имеет большую длину, чем абсолютно минимальное дерево (например, если ЛХ вершины правильного треугольника, то абсолютно минимальная сеть состоит из трех отрезков, соединяющих центр этого треутольника с его вершинами, а минимальное основное дерево состоит из двух сторон треугольника). Однако, как мы уже отмечали, задача поиска абсолютно минимального дерева является Л'Р-трудной, поэтому большое практическое значение имеет построение приближенных решений этой задачи.
Один из самых распространенных способов состоит в построении минимального остовного дерева. Поэтому важно, с одной стороны, уметь как можно быстрое строить минимальные остовные деревья, а с другой стороны уметь оценивать, на сколько длина минимального остовного дерева может отличатыж от длины абсолютно минимального дерева. Задача о поиске минимального остовного дерева легко сводится к задаче об остове минимального веса во взвешенном графе.
В самом деле, пусть Л1 произвольное множество, состоящее из и точек плоскости. Построим линейную реализацию полного графа К„, соединив каждую пару точек ЛХ, и ЛХ. из ЛХ отрезком. Превратим граф К„во взвешенный, положив ю(е, ) = ~ЛХ,ЛХ ~, где е, ребро графа К„, соединяющее вершины, соответствующие ЛХ, и ЛХз. Очевидно, что остов минимального веса взвешенного графа К„с весовой функцией ы совпадает с минимальным остовным деревом, затягивающим множество Введение. 20 ЛХ. Поэтому, для построения минимального остовного дерева можно использовать, например, полиномиальный алгоритм 1;раскала 16Ц, см.
ниже, которыи приведет к успеху за 0(п ) операций. Заметим, однако, что при поиске остова минимального веса для произвольного полного взвешенного графа с и вершинами имеется п (и— 1)12 входных данных (веса ребер). тогда как в случае поиска минимального остовного дерева достаточно задать координаты и точек на плоскости (граничных вершин), т.е.
количество входных данных равно 2п. Это наводит на мысль. что можно построить более быстрый алгоритм поиска минимального остовного дерева, используя геометрию этой задачи. Такой ътгоритм действительно существует, Оказывается, при поиске очередного ребра е;+г минимального веса достаточно перебирать лишь ребра так называемой триангуляции Делоне граничного множества, что позволяет существенно сократить чисю операций (Шеймос, 1761).
А именно, с помощью триангуляции Делоне удается построить алгоритм, строящий минимальное остовное дерево за 0(п 1я и) операций. Триангуляция Делоне и диаграмма Вороного Триангуляция Делоне тесно связана с так называемой диаграммы Вороного конечного множества точек плоскости. Пусть ЛХ с К~ такое многкество. Многоугольником Вороного точки ЛХ; мнолсества М называется множество Л'ог(ЛХ,), состоящее из всех таких точек плоскости, расстояние до которых от точки ЛХ; не больше, чем до лгобой другой точки множества М: Л~ог(ЛХ,) = 1Х Е й ! ((ХЛХ;(! < ~ЙХЛХг(1 Х ~ 1).
Ясно, что многоугольник Вороного точки ЛХ, представляет собой пересечение замкнутых полуплоскостей П., Х ~ г, где полуплоскость П . содержит точку ЛХ, и ограничена серединным перпендикуляром к отрезку ЛХ,М.. Поэтому Ъог(Л4) является выпуклым многоугольником (возможно, неограниченным). Построив для каждой точки ЛХ; из множества ЛХ ее многоугольник Вороного, мы получим разбиение плоскости в объединение выпуклых многоугольников, которое называется диаграммой Вороно~о мнолсества ЛХ. Вершины многоугольников Л'ог(ЛХ,) называются вершинами диаграммы Вороного, а их ребра ребрами диаграммы Вороного.,Ясно, что кагкдое ребро диаграммы Вороного принадлежит ровно двум многоугольникам Вороного. Приведем несколько важных свойств диаграммы Вороного.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
