4488
правок
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
(не показаны 2 промежуточные версии этого же участника) | |||
Строка 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>? | ||
== См. также == | == См. также == |
правок