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

'''Теорема 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].

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