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

(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.

Следующий результат задает верхнюю и нижнюю границы A(S).

'''Теорема 3 [4]. Для каждого конечного множества точек S выполняется соотношение <math>\Delta(S) < 1.678 \;</math>.'''

Для доказательства верхней границы заменим каждую вершину шестиугольной черепицы <math>\mathbb{R}^2 \;</math> определенной замкнутой кривой Зиндлера (по определению, все пары точек, делящие пополам периметр кривой Зиндлера, находятся на одинаковом расстоянии). В результате получаем сеть <math>G_F \;</math> с геометрической протяженностью, приблизительно равной 1.6778, см. рис. 3. Пусть дано конечное множество точек S. Применим небольшую деформацию к масштабированной версии <math>G_F \;</math>, такую, чтобы все точки S лежали в конечной части, G, деформированного множества. Согласно теореме Дирихле о приближении действительных чисел рациональными, достаточно выполнить деформацию, малую относительно размера ячейки, так что на протяженность она не повлияет. Определение и свойства кривых Зиндлера см. в [8].

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