Классификация локально минимальных плоских сетей с выпуклыми границами (1097579), страница 6
Текст из файла (страница 6)
для решетки, составленной из всех вершин вида [т, и», где 1 < пь, < 2ь и 1 < ьь < 2 . Ота гипотеза была доказана в [2]. Так как рсзультатьь австралийской школы требуют для своей формулировки введения многих новых понятий, описывающих структуру абсолютно минимальных сетей, мы пе будем приводить, их з,лесьь а ограни ьимся сделанными ссылками и некоторыми примерами, приведеппьпли на рис. 10. Лбсолотно минимальные сети 20 Рассмотрим все сети, затягиваклцпе множество ЛУ, такие что каждая вершина сети принадлежит ЛУ. Сеть напменыпей длины среди этого семейства сетон называется .ипяплпльны.я оспщеяьхи дгревои. Ясно, что полученная есть, вообще говоря, имеет большую длину, чем абсолютно минимальнос дерево [наприхюр, если ЛХ вершины правильного треугольника, то абсолютно минимальная сеть состоит из трех отрезков, соединяющих центр этого треуч ольника с его вершинами, а минимальное основное дерево состоит из двух сторон треугольника).
Однако этот подход оказывается весьма эффективным по целому ряду причин. Во-первых, существуют быстрые алгоритмы построения минимальных остовных деревьев, во-вторых, длина мипцмального остовпого дерева, оказывается, нс может сильно отличаться от длины абсолютно минимально~ о дерева [см. следующий параграф). В-третьих, минимальные остовные деревья интересны сами по ссбс, поскольку используются 'при кластеризации, при вычислении характерной размерности множества точек, при распознавании образов, для минимизации длины проводников при компоновке электричщ кой сх~ мы ОВл1' и т.л.
[см. [31]). Задача о поиске минимального остовного дерева легко сводится к зада|с об остове минимального веса во взвешенном графе. В самом деле, пусть ЛУ произвольное множество, состоящее из и точек плоскости. Построим линейную реализацию полного графа К„, соединив каждую пару точек И, и ЛУ, из ЛУ отрезко л. Превратим граф Ка во взвешенный, положив ы[с, ) = ЛУ;М [, где еб ребро графа Л„, соединяющее вершины, соответствуютцис ЛУ, и ЛУ.. О аспидно, что остов мцпимального веса взвешенного графа [УУ„,щ) совпадает с минимальным остовпым деревом, затягивающим множество ЛХ. Поэтому, для построения минимального остовного дерева можно использовать, например, полпномиальный алгоритм Крас- кала [2в], который приведет к успеху за 0[па) операций.
За летим, однако, что при поиске остова минимального веса для произвольного полного взвешенного графа с и вершинами имеется п[п — 1)/2 входных данных [веса ребер), тогда как в случае поиска мцннмального остошюго дерева лостато шо задать координать~ и то гек на плоскости (грани юных вершин).
!1то наводит на мыслгь что мспхпо построить более эффективный а.п'оритм поиска минимального остовнот о дерева, используя геометрию этой задачи. Такой алгоритм действительно существует. Оказывается, при поиске очередного ребра еьь~ минимального веса достаточно перебирать лишь ребра так называемой триангуляции '[елене [Шеймос, [39]) граничного множества, что позволяет существенно сократить число операций. Л именно, с помощью триангуляции Делоне удается построить алгоритм, строящий минимальное остовное дерево за 0[п1д и) операции. Лбсошотно минимальные сети 3.1 Триангуляция Делоне и диаграмма Вороного Х(ля того, чтобы определить триаш уляпию Делоне, удобно начать с так называемой диаграммы Вороного конечного мнол<ества точек плоскости. Пусть И С .Лз такое множество.
Многоугольником Вороного точки М, множ«тва ЛХ называется множество Чог(ЛХ<), состоящее из всех таких точек плоскости, расстояние до которых от то экн Л1, не больше, чем до ээюбоя лруэ ой гочки мпожестээа ЛХ: Чог(И,) = (Х Е тй ~ ХМ,~ ( !ХИэ~, Э ф э). Ясно, гго многоугольник 13ороного точки М, представляет собой пересечение замкнутых полуплоскостсй 11, 3 ф э, где полуплоскость П содержит точку М, и ограничена середяяным перпендикуляром к отрезку И,М,. По;этому Чог(И;) является выпуклым многоугольником (возможно, неограниченным) .
Построив для каждой точки Л1, из множества М ее многоугольник Вороного, мы получим разбиение плоскости в объединение выпуклых многоугольников, которое называется диаграммой 1Зороиого множеспша М. Вершины многоугольников Чог(М<) называются есршинаэси диаграммы Вороного, а их ребра ребрами диагра.имы Вороного.
Ясно, что каждое ребро диаграммы Вороного принадлежит ровно двум многоугольникам Во!эоног о. Приведем несколько важных сээойств диаграммы !3ороного. Чтобы упростить формулировки, мы будем предполагать, что множество ЛсХ находится в общем положении в следующем смысле: никакие четыре точки из ЛХ не леэкят на однон сээ<!эуэкэссэсэээ и никакие трн точки из М не леэяат на ос!ной прямой. утвсэ1эждони<э 10 В еде<с<нина прсдсюэсэжениял, г каждой герэаине диа- граммы Вороного < тыкустся ровно три ес ребра.
Хаким образом, каждая вершина э' днщ раммы !3ороного мпожес ыэа ЛХ является центром окружности С(Г), на которой лежат ровно три точки пз апэожес "э на ЛХ. Утверждение 11 Внутри круга, ограниченного окружносэаьт С(1'), нс содержится точек из иноисестеа И. Построим теперь плоский граф ХЭ(ЛХ), двойственный к диас рамме Вороного, взяв в качестве множества вершин < рафа тэ(сЭХ) множество ЛХ. Пара вершин М„и Л1 графа ХЭ(ЛХ) смежны и соединены отрезком ЛХ,И ребром < рафа ХЭ(ЛХ), тогда и только тогда, когда многоуэ ольники Вороного Чог(М,) и Чог(ЛХ ) имен<и общее ребро. !с!мест место следусощий вьмкный результат, доказанный Делоне ~9). йбсолотно минимальные сети э'творжденио 12 В сделанныя предполоэиениях, гХэад57У[М) является три- ангуьяциеи',нноэюестьа ЛХ.
Определение, Граф 7? [ЛХ) называется триангуляцией Делоне множества ЛХ. Замечаниев Из сказанного выше вытекает, что триангуляция Делоне множества М обладает следующим свойством: вну три окружности. описанной вокруг произвольного треугольника триангуляции, вет точек из М. Оказывается, это свойство можно принять за определение триангуляции Делоне. Такое определение уже ие требует предположения о том, что точки множества ЛХ находятся в общем положении. Ясно, как в этом случае получить триангуляиию Делоне из диаграьлмы Вороного. !Лели построить граф Хэ(ЛХ) для произвольного миожсства точек, то у него, вообще ь оворя, могут получиться ограниченные грани с числом вершин больше чем 3.
Однако, очевидно, все всрпиипа каэкдой такой граии расположены иа иекоторой окруэкиости [с центром в соответствующей вершине диаграммы Вороного), внутри которой вет точек из мяожества М. Поэтому, пабы завершить иостросиис триангуляции в этом случае, достаточно дополнить граф Хэ[ЛХ) ребрами произвольных триангуляций диагоналями его ветрсугольных ограниченных граней. Приведем теперь результат !Иеймоса. связывающий триангуляции Делоне и мииимсыьвьэми остовиыми деревьями. Предложоиио 8 Пдсгиь М проиэеольное конечное мноэкестео точек плоскости, и Г нскогиорое лшни.нильнос остоенос дсрсео, затягиеаюн5се ЛХ.
Тогда ребра Г яеляючнся ребэраыи триангузяиии Делоне. 7У[ЛХ) мноэн:естиа М. Итак, каэкдое мииимальяос остовяос дерево, затягивающсс коисчиос множество то )ек плоскости, является подграфом три выл уляции Делоне этого множества. 5Иы ве будем щэиводить здесь алгоритм, позволяющий быстро [а именно, за О(и!,„п) операций) построить триавгуляцию Делоне миолссства М, состоящего из и точек плоскости. Этот алгоритм подробно изложен в [;54]. Исходя из триангуляции Делоне, можно построить минимальиос остовиос дерево за и операций.
Подводя итоги, сформулируем следующяя результат П!еймоса [35!]. Предложение 9 (Шоймос) ЛХинимальнос остоонос дсреоо, эатяеиааюи5се,иножесэпео, состояьцес- иэ и точен" плоскосспи, моясео~ быть построено эа опта.вильное время порядка 0[и! и) операций.
Абсошотно минимальные сети 4 Отношение Штейнера В предыдущем разделе мы рассказали про то, как можно быстро построить приближение для абсо.потно минимального дерева, т,е. мииимальнос остовное дерево. Однако мало научиться строить какое-то приближенное !эсшение, ие менее важно попятяэ насколько сильно построенное приближение отличается от точного решения. Пусть имеется некоторый алгоритм А, строящий для произвольного множества ЛХ точек плоскости некоторую сеть А[ЛХ), эатягиваюшук> Л1, которую мы хотим рассматривать как приближенное решение задачи П!тсйясра. Обозначим через Х., [М) длину этой сети, а через Х,[ЛХ) длину абсолютно минимального дерева лля ЛХ.
Тогда величину р, = !п1[Х.з [ЛХДХ„[М)), где нижняя грань берется по всевозможным конечным множествам ЛХ точек плоскости. естественно рассматривать как характеристику 'хорошести" приближений, получаемых с помощью алгоритма А. Очевидно, что 0 < р„< !. Алгоритм А тем лучше, чем ближе число ра к 1. Поэтому вычисление р, для конкретных приближеиии представляет собой важную, однако очсиь сложную задачу. Если в качестве а.п оритма А взять построеяие минимальнос о остовпого дерева, то соответствующее число ро известно в литературе кяк отнотснис- ХХ!тсннсро и обы шо обозначается просто через р. Иногда бывает удобно определить также отиошеппе П1тейвера р[н) для множеств ЛХ, состоящих из и точек плоскости. В ! 968 году 1'илбсрт и Поллак [22) вычислили отношение !Птсйнера р[3) для ашожеств, состоящих из трех точек.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
