Связь вида нормы и геометрии минимальных сетей (1104796), страница 8
Текст из файла (страница 8)
Если добавить луч r0 к вырожденному ежумежду его соседними лучами ri и ri+1 (так, чтобы r0 оказался внутри неразвернутого угла между ri и ri+1 ), две новые пары соседних лучей, {ri , r0 } и {r0 , ri+1 } будутвырожденными, поскольку соответствующие им смежные углы будут содержатьсмежный угол, соответствующий паре {ri , ri+1 }.Пусть k · k1 и k · k2 — две нормы на двумерной плоскости такие, что множествадеревьев SM T (M ) в них совпадают для любого граничного множества M . Будемназывать единичные ежи в нормах k · k1 и k · k2 соответствующими друг другу,если они соответствуют одному ежу.Для краткости, будем называть просто ежами встречающиеся единичные ежи,вырожденные ежи и вырожденные единичные ежи там, где это не вызовет разночтений.Теорема 2.4 Пусть даны k · k1 и k · k2 — две строго выпуклые дифференцируемые нормы на двумерной плоскости такие, что деревья SM T (M ) в них совпадают для любого граничного множества M .
Тогда для произвольного вырожденногоежа в любой из двух норм соответствующие ему единичные ежи в этих нормахгомотетичны.Доказательство. По лемме 2.12, из того, что деревья SM T (M ) в нормах k · k1и k · k2 совпадают для любого граничного множества M следует, что множестватройников в этих нормах также совпадают. Поскольку вырожденность ежа в данной норме зависит только от множества тройников в ней, имеем, что еж вырожденв одной из двух данных норм тогда и только тогда, когда он вырожден и во второй42из двух данных норм.
Далее в доказательстве будем называть вырожденный еж водной из двух данных норм просто вырожденным ежом.Зафиксируем произвольный вырожденный еж с началом в нуле и возьмем егоединичный еж в норме k · k1 . Для каждого единичного вектора v из единичногоежа такого, что −v не принадлежит единичному ежу, добавим −v в единичныйеж, и далее будем рассматривать получившийся единичный еж, обозначим его H̄(заметим, что он остался вырожденным). Пронумеруем все вектора H̄ по кругу,от v1 до v2n . Выберем любую точку на плоскости, назовем ее A1 . Отложим векторv1 от A1 , получим новую точку A2 .
Аналогично отложим v2 от A2 , получив A3 ,v3 от A3 , получив A4 и т.д. В итоге, отложив v2n от A2n , мы замкнем ломаную(поскольку сумма всех векторов из H̄ равна нулю).Покажем, что построенная ломаная является периметром выпуклого многоугольника и не имеет самопересечений. Действительно, пусть самопересечение есть.Тогда найдется ломаная, состоящая из n + 1 ребра подряд в круговом порядке построенной замкнутой ломаной, которая содержит оба пересекающихся ребра. Покажем, что ни одна ломаная, состоящая из n + 1 ребра подряд в круговом порядкепостроенной замкнутой ломаной, не имеет самопересечений. Рассмотрим произвольный вектор из ежа и изменим координаты, чтобы он был направлен по осиOX, и построим n + 1 ребро начиная с него. У всех векторов, кроме первого ипоследнего, проекция на ось OY положительна.
А первое и последнее ребро параллельны прямой OX и тоже не пересекаются с другими ребрами ломаной. Получается, что мы имеем замкнутую ломаную без самопересечений, все углы которойориентированы в одну сторону. Значит, имеем выпуклый многоугольник.Таким образом, мы построили центрально симметричный 2n-угольник с равными в норме k · k1 сторонами; множество его вершин обозначим через M (иногда саммногоугольник тоже будем называть M ), его центр обозначим через O. Равномерно подразобьем стороны M с мелкостью разбиения ε. Полученную конструкцию(а также — полученное множество точек) будем обозначать как M ε .
Покажем, чтосуществует ε > 0 такой, что для всех M ε в норме k · k1 SM T на них будет выгля-43деть как периметр M ε с любым одним отсутствующим ребром между соседнимивершинами.Покажем сначала, что у SM T (M ε ) для некоторого ε и всех меньших не существует невырожденных (бинарных) компонент, состоящих более чем из одногоребра.Докажем от противного. Заметим, что по лемме 2.11 все ребра SM T (M ε ) имеютдлину меньше ε. Зададим величину ` следующим образом. Проведем из O отрезки ввершины и середины сторон M . На каждом отрезке до вершины рассмотрим минимум расстояний (измеренный в норме k · k1 ) до периметра M без учета двух сторон,инцидентных концу отрезка.
На каждом отрезке до середины стороны рассмотримминимум расстояний до периметра M без учета стороны с выбранной серединой. `возьмем как минимум рассмотренных величин (` получится больше нуля). Введемрасстояние между вершинами M ε в круговом порядке: считаем его как меньшееиз двух количеств вершин на двух дугах, на которые две данные вершины делятпериметр M ε . Рассмотрим наиболее удаленные друг от друга в круговом порядкевершины X и Y из M ε , соединенные невырожденной компонентой SM T .
Разберемслучаи.1) X и Y лежат на одной стороне исходного многоугольника M , пусть на A1 A2 .Рассмотрим самую далекую от прямой A1 A2 подвижную вершину данной невырожденной компоненты. Рассмотрим полуплоскость не имеющую пересечений спрямой A1 A2 , границей которой является прямая, содержащая самую далекуювершину и параллельная прямой A1 A2 .
По лемме 2.4, одно из трех инцидентныхей ребер идет в рассматриваемую полуплоскость, попадая в граничную вершинуZ, расположенную еще дальше от прямой A1 A2 , чем она сама (в противном случае выбранная вершина не будет самой далекой). Z не лежит на малой дуге XY(меньшей из двух частей периметра в смысле количества вершин M , на которые Xи Y разбивают периметр), поскольку не может принадлежать прямой A1 A2 .
Получается, что мы нашли вершину Z из той же невырожденной компоненты снаружималой дуги XY . Хотя бы одно из расстояний в круговом порядке среди XZ или44Рис. 6: элемент разбиения α и его образ при параллельном переносе (пунктиромпоказаны их границы).Y Z больше расстояния в круговом порядке XY . Получаем противоречие с тем, чтоX и Y — наиболее удаленные в круговом порядке вершины M ε , принадлежащиезаданной невырожденной компоненте.2) X и Y лежат на соседних сторонах, пусть на A1 A2 и A2 A3 соответственно(см. Рис. 6).Из-за вырожденности ежа H̄ найдется такой тройник с началом в A2 , что одиниз элементов разбиения плоскости этим тройником окажется внутри неразвернутого угла между лучами [A2 A1 i и [A2 A3 i (обозначим этот элемент за α). Рассмотримлюбую из неграничных вершин в пути по дереву между X и Y , обозначим ее заU1 (заметим, что U1 лежит во внутренности conv(M ε ) по лемме 2.4: в противномслучае принадлежности границе conv(M ε ) существовало бы ребро из нее вовнеconv(M ε )).
Параллельно перенесем α так, чтобы вершина U1 стала вершиной углаα. По лемме 2.9, хотя бы одно из ребер, инцидентных U1 , лежит в замыкании ᾱ. Заметим, что второй конец U2 этого ребра не может оказаться граничной вершиной состорон A1 A2 или A2 A3 , поскольку замыкание перенесенного угла ᾱ не пересекаетсяс указанными сторонами. Повторив рассуждение c U2 вместо U1 , получим следующую вершину U3 , не являющуюся граничной вершиной со сторон A1 A2 или A2 A3 .Продолжая таким образом, из-за конечности количества вершин мы попадем награницу (то есть какая-то вершина Uk окажется граничной вершиной, не принадлежащей сторонам A1 A2 или A2 A3 ) и получим противоречие с тем, что X и Y —наиболее удаленные в круговом порядке вершины M ε , принадлежащие заданной45Рис.
7: закрашена область W1 . Пунктиром схематически изображены путь междуX и Y в невырожденной компоненте, а также минимальный по количеству реберпуть из J до части границы, принадлежащей W2 .невырожденной компоненте.3) X и Y не лежат ни на одной стороне, ни на соседних (см. Рис. 7).Пусть X (с точностью до перенумерации) лежит на стороне A1 A2 , а Y лежитна стороне Ak Ak+1 , где k ≤ n. Путь в невырожденной компоненте между X и Y делит многоугольник M (по площади) на области W2 (содержит B, середину A2 A3 ) иW1 (содержит C, середину An+2 An+3 — стороны, диаметрально противоположнойстороне A2 A3 ). Также путь пересечет как минимум одну из половин BC, OB илиOC.
Пусть, для определенности, он пересечет половину OC (случай BO разбирается полностью аналогично) в точке H (возможно, пересечений пути и хорды BCнесколько, тогда рассмотрим любое из них, и будем считать, что это пересечение споловиной OC). По лемме 2.13, не далее, чем в 4ε от H есть такой поворот пути (ввершине J), что третье ребро из J выходит в W2 . Заметим, что все граничные вершины, до которых можно дойти из J через третье ребро, лежат в W2 . Рассмотримту из них, путь до которой, измеренный в количестве ребер дерева, минимален(пусть в нем m ребер), и возьмем на этом пути вершину K, находящуюся в [ m2 ]ребер от J. Имеем m >`−4ε,εа значит, [ m2 ] >`−6ε.2εКоличество граничных вершин46в M ε равно2n,εно по лемме 2.10, минимальное расстояние до границы, измерен-ное в количестве ребер, не может превосходить log22n,3εа у K оно не менее`−6ε,2εпротиворечие при достаточно малых ε.Таким образом, мы показали, что для некоторого ε > 0 граничное множествоM ε обладает полностью вырожденным SM T в норме k · k1 .
В этом случае, любоеребро SM T имеет длину, большую либо равную ε (поскольку расстояние междулюбыми двумя граничными вершинами ≥ ε, а промежуточных вершин в деревенет). Значит, длина SM T ≥2n−ε,εа описанная в начале доказательства топологияреализует нижнюю грань оценки.Значит, в норме k · k2 SM T будет также выглядеть как периметр M ε с любымодним отсутствующий ребром между соседними вершинами. Это означает, что всеребра M ε равны в k·k2 , что влечет гомотетичность соответствующих вырожденныхединичных ежей в k · k1 и k · k2 , чтд.Замечание. По сути, техника разбора случая 2 теоремы 2.4 есть ни что иное,как доказательство свойства клина (Wedge property, см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
