4446
правок
Геометрическая протяженность геометрических сетей: различия между версиями
Перейти к навигации
Перейти к поиску
м
Геометрическая протяженность геометрических сетей (посмотреть исходный код)
Версия от 21:56, 19 января 2018
, 19 января 2018нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 72: | Строка 72: | ||
'''Теорема 3 [4]. Для каждого конечного множества точек S выполняется соотношение <math>\Delta(S) < 1.678 \;</math>.''' | '''Теорема 3 [4]. Для каждого конечного множества точек S выполняется соотношение <math>\Delta(S) < 1.678 \;</math>.''' | ||
Для доказательства верхней границы заменим каждую вершину шестиугольной черепицы <math>\mathbb{R}^2 \;</math> определенной замкнутой кривой Зиндлера (по определению, все пары точек, делящие пополам периметр кривой Зиндлера, находятся на одинаковом расстоянии). В результате получаем сеть <math>G_F \;</math> с геометрической протяженностью, приблизительно равной 1 | Для доказательства верхней границы заменим каждую вершину шестиугольной черепицы <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? Чему равняется точное значение sup{<math>\Delta(S) \;</math>; S finite}? | ||
== См. также == | == См. также == | ||