4488
правок
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
(не показаны 3 промежуточные версии этого же участника) | |||
Строка 28: | Строка 28: | ||
== Основные результаты == | == Основные результаты == | ||
'''Теорема 1 [4]. Обозначим за <math>S_n \;</math> множество | '''Теорема 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>.''' | ||
Строка 35: | Строка 35: | ||
[[Файл:GDGN_1.png]] | [[Файл:GDGN_1.png]] | ||
Рисунок 1. Вложения с минимальной протяженностью | Рисунок 1. Вложения с минимальной протяженностью для регулярных множеств точек | ||
Строка 53: | Строка 53: | ||
Для точек, | Для точек, находящихся в общем положении, вычисление геометрической протяженности оказывается весьма сложным. Решение этой задачи полностью известно только для множеств S = {A, B, C} величины 3. | ||
Строка 67: | Строка 67: | ||
Следующий результат задает верхнюю и нижнюю границы | Следующий результат задает верхнюю и нижнюю границы <math>\Delta (S) \;</math>. | ||
'''Теорема 3 [4]. Для каждого конечного множества точек S выполняется соотношение <math>\Delta(S) < 1 | '''Теорема 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]. | ||
Строка 89: | Строка 89: | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Для практического применения в дополнение к верхним границам геометрической протяженности пригодились бы верхние границы веса (т.е. общей длины ребер) геометрической сети. Некоторые теоретические вопросы также требуют дополнительного исследования. Всегда ли <math>\Delta(S) \;</math> достигается для конечной сети? Как вычислить (точно или приближенно) <math>\Delta(S) \;</math> для заданного конечного множества S? Чему равняется точное значение | Для практического применения в дополнение к верхним границам геометрической протяженности пригодились бы верхние границы веса (т.е. общей длины ребер) геометрической сети. Некоторые теоретические вопросы также требуют дополнительного исследования. Всегда ли <math>\Delta(S) \;</math> достигается для конечной сети? Как вычислить (точно или приближенно) <math>\Delta(S) \;</math> для заданного конечного множества S? Чему равняется точное значение <math> sup \{ \Delta(S); S \; finite \}</math>? | ||
== См. также == | == См. также == |
правок