Геометрическая протяженность геометрических сетей: различия между версиями

(2) <math>\delta(G) := sup_{p \ne q \in G} \delta(p, q)</math>.

Это определение отличается от понятия коэффициента растяжения, использовавшегося в контексте остовных деревьев; подробнее об этом – в монографиях Эпштейна [6] или Нарасимхана и Смида [11]. В последней рассматриваются только пути между вершинами <math>p, q \in V \;</math>, тогда как понятие геометрической протяженности включает также все точки на ребрах. Следовательно, коэффициент растяжения треугольника T равен 1, однако его геометрическая протяженность задается формулой <math>\delta(T) = \sqrt{2 / (1 - cos \; \alpha)} \ge 2</math>, где <math>\alpha \le 60^\circ \;</math> - самый острый угол T.

<math>\Delta(S) := inf \{ \delta(G); G \;</math> – конечная плоская геометрическая сеть, содержащая S}

Теорема 1 [4]. Обозначим за Sn множество углов правильного n-угольника. Тогда A(S$) = 2/'л/з, (S4) = p2 и A(Sn) = jr/2 для всех n> 5.

Лемма 1. Пусть T – дерево, содержащее Sn. Тогда S(T) > nln.

[[Файл:GDGN_1.png]]

Лемма 2. Обозначим за C простую замкнутую кривую на плоскости. Тогда S(C) > nil.

Очевидно, для круга лемма 2 выполняется со знаком равенства. Из следующей леммы следует, что круг – единственная замкнутая кривая, имеющая минимальную геометрическую протяженность ж/2.

Лемма 3 [3]. Обозначим за C простую замкнутую кривую на плоскости с геометрической протяженностью < л /2 + e(<5). В таком случае C содержится в кольце ширины 8.

 

 

Теорема 2 [5]. Плоская геометрическая сеть с минимальной геометрической протяженностью, содержащая три заданные точки {A, B, C}, представляет собой либо отрезок прямой, либо дерево Штейнера, представленное на рис. 1, либо простой путь, состоящий из двух отрезков прямых и одного сегмента экспоненциальной спирали, см. рис. 2.

[[Файл:GDGN_3.png]]

Теорема 3 [4]. Для каждого конечного множества точек S выполняется соотношение A(S) < 1:678.

Для доказательства верхней границы заменим каждую вершину шестиугольной черепицы R2 определенной замкнутой кривой Зиндлера (по определению, все пары точек, делящие пополам периметр кривой Зиндлера, находятся на одинаковом расстоянии). В результате получаем сеть GF с геометрической протяженностью 1:6778, см. рис. 3. Пусть дано конечное множество точек S. Применим небольшую деформацию к масштабированной версии GF, такую, чтобы все точки S лежали в конечной части, G, деформированного множества. Согласно теореме Дирихле о приближении действительных чисел рациональными, достаточно выполнить деформацию, малую относительно размера ячейки, так что на протяженность она не повлияет. Определение и свойства кривых Зиндлера см. в [8].

Теорема 4 [3]. Существует конечное множество точек S, такое, что A(S) > (1 + КГп)л72.

Теорема 4 выполняется для множества точек S размером 19 x 19 вершин целочисленной решетки. Грубо говоря, если S заключено в геометрическую сеть G с протяженностью, близкой к it /2, то, согласно лемме 3, границы граней G должны быть заключены в небольшом кольце. Для получения внутреннего и внешнего кругов этого кольца следует воспользоваться утверждением Купербергов и др. [9], гласящим, что расширение упаковки дисков радиуса < 1 на определенный коэффициент не может покрыть квадрат со стороной 4.

Для практического применения в дополнение к верхним границам геометрической протяженности пригодились бы верхние границы веса (т.е. общей длины ребер) геометрической сети. Некоторые теоретические вопросы также требуют дополнительного исследования. Всегда ли A(S) достигается для конечной сети? Как вычислить (точно или приближенно) A(S) для заданного конечного множества S? Чему равняется точное значение sup{A(S); S finite}?