Геометрические свойства локально минимальных сетей (1097521), страница 6
Текст из файла (страница 6)
Чтобы упростить формулировки, мы будем предполагать, что множество ЛХ 2. Абсолютно минимальные сети. 21 находится в общем положении в следующем смысле: никакие четыре точки из ЛХ не лежат на одной окружности, и никакие трн точки из ЛХ не, лежат яа одной прямой.
Ъ"тверждеиие В.10 В сделанных предположениях, в каждой вершине. диаграммы, Вороного гтыкутпся ровно тра ее ребра. Таким образом, каждая вершина 1г диаграммы Вороного множества М яьтяется центром окружности С(Ъ'), на которой лежат ровно трн точки из множества ЛХ. Утверждение В.11 Внутри круга, ограниченного окружностью С(1г), ня содержипкя, точек из множесгпва М. Построим теперь плоскии граф Р1М), двойственный к диаграмме Вороного, взяв в качестве множества вершин графа Р(ЛХ) множество ЛХ. Пара вершин М; и ЛХ, графа Р( М) смежны и соединены отрезком ЛХ,ЛХ~ ребром графа Р(ЛХ), тогда и только тогда, когда многоугольники Вороного Ъог(ЛХ,) и Луог(ЛХ ) имеют общее ребро.
Имеет место следующий важный результат, доказанный Делоне [13). Ъ'тверждение В.12 В сделанных предположениях, градХ Р(ЛХ) явля- ется триангуляцией множества М. Определение. Граф Р(ЛХ) называется триангуляцией Делоне множе- ства М. Из сказанного выше вытекает., что триангуляция Делоне множества М обладает следующим свойством; внутри окружности, описанной вокруг произвольного треугольника триангуляпии, нет точек из ЛХ.
Оказывается. это свойство можно принять за определение триангуляции Делоне. Такое определение уже не требует предположения о том, что точки множества ЛХ находятся в общем положении. Ясно, как в этом случае получить триангуляцию Делоне из диаграммы Вороного. Если построить граф Р(ЛХ), двойственныи к диаграмме Вороного Ъог(ЛХ) произвольного множества ЛХ, то у графа Р(ЛХ), вообще говоря, могут получиться ограниченные грани с числом вершин больше чем 3, Однако, очевидно, все вершины каждой такой грани расположены на некоторой окружности (с центром в соответствующей вершине диаграммы Вороного), внутри которой нет точек из множества ЛХ.
Поэтому, чтобы завершить построение триангуляции в этом случае, достаточно дополнить граф ТМ,ЛХ) ребрами произвольных триангуляций диагоналями его нетреугольных ограниченных граней. Приведем теперь 1эсзультат Шеймоса, связывающий триангуляции Делоне и минимальные остовные деревья. Введение. 22 Предложение В.7 Пусть ЛХ .. произвольное конечное множество точек плоскости, и Г -- некоторое минимальное остповное дерево, зашлгивающее М.
Тогда ребра Г лвляютсл ребрами триангуляции Делоне Р(ЛХ) множества М. Итак, каждое минимальное остовное дерево, затягивающее конечное множество точек плоскости, является подграфом триангуляции Делоне этого множества. Мы не будем приводить здесь алгоритм, позволяющий быстро (а именно, за 0(п 1я и) операций) построить триангуляцию Делоне множества М, состоящего из и точек плоскости.
Этот алгоритм подробно изложен, например, в 169). Исходл из триангуляции Делоне, можно построить минимальное остовное дерево за и операций. Подводя итоги, сформулируем следующий результат Шеймоса 176). Предложение В.8 (Шеймос) Минимальное остовное дерево, затягивающее множество, состоящее из а точек плоскости, может быть построено за оптимальное время порядка 0(п18п) операций.
Отношение Штейиера В предыдущем разделе мы рассказали про то, как можно быстро построить приближение для абсолютно минимального дерева, т.е. минимальное остовное дерево. Однако, как мы уже отмечали, мало научиться строить какое-то приближенное решение, не менее важно понлть, насколько сильно построенное приближение отличается от точного решения.
Пусть имеется некоторый алгоритм А, строящий для произвольного множества ЛХ точек плоскости некоторую сеть А(М), затягивающую ЛХ, которую мы хотим рассматривать как приближенное решение задачи Штейнера. Обозначим через Х, (ЛХ) длину этой сети, а через Х„(ЛХ) длину абсолютно минимального дерева длл ЛХ. Тогда, очевидно, число Е,(ЛХ)/Хь(ЛХ) не превосходит 1, и оно тем меныпе, чем алгоритм А хуже, т.е, чем построенное алгоритмом А дерево сильнее отличается от абсолютно минимального дерева.
Величину р„= ифли„.1ЛХ)ХХ„(ЛХ)), где нижняя грань берется по всевозможным конечным множествам М точек плоскости, естественно рассматривать как характеристику "хорошести" приближений, получаемых с помощью алгоритма А. Очевидно, что 0 ( рь < 1, Ясно., что алгоритм А тем лучше, чем ближе число р„к 1. Поэтому вычисление р„для конкретных приблилсений представляет собой важную, однако очень сложную задачу. 3. Локально минимальные соти. 23 Если в качестве алгоритма А взять построение минимального остов- ного дерева, то соответствующее число р, известно в литературе как ошношение ХХХтейнера и обычно обозначается просто через р.
Иногда бывает удобно определить также отношение Штейнера р(п) для множеств ЛХ, состоящих из п точек плоскости. В 1968 году Гилберт и Поллак [30) вычислили отношение Штейнера р(З) для множеств, состоящих из трех точек. Л именно, они показали, что р(3) = 1пХ (Х,(ЛХ)/Хо„(ЛХ)) = ъ'3/2, и = 1 л, в, с у с н'" где через Х, (ЛХ) обозначена длина минимального остовного дерева, затягивающего множество ЛХ. Так как, очевидно, р < р(3), получаем следующую оценку: р < у/3/2. В той же работе Гилберт и Поллак выдвинули следующую гипотезу.
Гипотеза (Гилберт, Поллак) Отношение Штейнера р равно Л/2 = 0,8660254... Эта гипотеза была доказано только в 1990 году Ду и Хвангом. Предложение В.9 (Ду, Хванг) Гипошеэа Гилберта — Ползано верна, а ниенна р = у/3/2. Отметим, что за доказательство этого результата шла упорная борьба.
С одной стороны, вычислялись чиста, р(п) для малых и. Поллак [67) показал, что р(4) = у/3/2, т.е. доказал, что гипотеза справедлива для множеств ЛХ, состоящих из и = 4 точек. Ду, Хванг и Яо [22) доказали, что р(5) = у/3/2, а затем Рубинштейн и Томас [72) --- распространили этот результат на случай п = 6, вычислив р(6). С другой стороны предпринимались попытки получить опенки снизу на р. Гилберт и Поллак сообщают [30), что Моор установил справедливость неравенства 0,5 < р. Затем оценка последовательно улу.чшалась так: Грэхем и Хванг 0,57 < р; Чанг и Хванг 0,74 < р; Ду и Хванг 0,8 < р; Чанг и Грэхем 0,824 < р. Таким образом, борьба пошла уже за сотые и тысячные. Наконец, спустя 22 года, блестящие работы Ду и Хванга [17) и [18] поставили точку в истории этой задачи.
3 Основные результаты теории локально минимальных сетей Локально минимальные сети возникают как естественное расширение класса абсолютно минимаяьных сетей. Как уже отмечаюсь вышс, локально минимальные сети неявно возникли при изучении абсолютно Введение.
24 минимальных сетей на плоскости: именно локально минимальные сети перебирает алгоритм Гбелзака, строящий абсо:потно минимальную сеть, затягивающую фиксированноо конечное множество за точек плоскости. Переход к изучению локально минимальных сетей на плоскости позволяет получить рлд нетривиальных результатов, которые. в частности, дают возможность существенно сократить перебор возможных топологий при построении абсолютно минимального дерева. Отметим, что с локальной точки зрения локально минимальные сети устроены точно так же как абсолютно минимальные.
Изучение локально минимальных сетей на других римановых многообразиях также представляет интерес. Здесь особое внимание в литературе уделяется исследованию замкнутых (без фиксированной границы) локально минимальных сетей на замкнутых поверхностях с метрикой постоянной кривизны. 3.1 Плоские локально минимальные бинарные деревья с выпуклой границей Класс бинарных деревьев является основным при изучении абсолютно минимальных деревьев, так как каждое такое дерево Г представимо в виде объединения минимальных бинарных деревьев.
стыкующихся между собой в ряде вершин степени 2. Поэтому важной проблемой является изучение свойств плоских локально минимальных бинарных деревьев. В серии работ Г42], ~43], ~45] Л. Л. Тужилиным совместно с автором получена полная классификация локально минимальных бипарных деревьев с выпуклой границей-.
Мы начнем с определения важного инварианта плоских бинарных деревьев. введенного в рассмотрение автором и Л. Л. Тужилиным в ]42], ~43], так называемого числа вращения. Пусть Г плоское бинарное дерево, (а,Ь) некоторая упорядоченная пара его ребер,и т единственный путь в Г, соединяющий эти ребра. Ориентируем путь Т от а к Ь, и пусть Р - произвольная вершина степени 3 дерева Г, лежащая внутри гб т.е, не совпадающая ни с одной из его концевых вершин.
Выберем круговую окрестность П вершины Р, такую что П П Г является деревом, не содержащим вершин из Г, отличных от Р. Тогда пересечение дП О Г состоит из трех точек, которые мы обозначим через А,, 1 = 1, 2, 3. Пусть а~ — первое, и аз - пос.яеднее ребро из Т, инцидентное Р, и пусть А; Е а,, 1 = 1, 2.
Рассмотрим дугу Ь окружности дП, лежащую между Аз и Аз и содержащую Аз. зати результаты не включены и основное содержание диссортании и прииодя гся здесь лишь для полноты литературного обзора. 3. Локально минимальные сети. 25 Если движение по дуге б от Л1 к Аэ происходит по часовой стрелке, то будем говорить, что мы поворачиваем направо в точке Р. В противном случае, скажем, что мы поворачиваем налево в точке Р. 1иелом вращения ьло(а,б) упорядоченной пары (а, Ь) ребер плоского бинарного дерева Г называется разность количества ф1, левых и количества 4АЛ правых поворотов во всех внутренних вершинах пути у: Ск]а,.б) = ф1 — 5гЛ. Определение. '1ислом вращения си Г бинарного дерева Г называется максиму.м чисел вращения йк(а, 6], взятый по всевозможным упорядоченным парам ребер из Г. Оказываетсл в терминах числа вращения молсно полностью описать все плоские локально минимальные бинарные деревья с выпуклой границей.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
