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

(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]. Обозначим за <math>S_n \;</math> множество углов правильного n-угольника. Тогда <math>\Delta(S_3) = 2 / \sqrt{3}, \Delta(S_4) = \sqrt{2}, \Delta(S_n) = \pi / 2 \;</math> для всех <math>n \ge 5 \;</math>.'''

Рисунок 1. Вложения с минимальной протяженностью в регулярные множества точек

Для точек, имеющих общее положение, вычисление геометрической протяженности оказывается весьма сложным. Решение этой задачи полностью известно только для множеств S = {A, B, C} величины 3.

[[Файл: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}?