4446
правок
Геометрическая протяженность геометрических сетей: различия между версиями
Материал из WEGA
Геометрическая протяженность геометрических сетей (посмотреть исходный код)
Версия от 09:46, 31 января 2018
, 31 января 2018→Основные результаты
Irina (обсуждение | вклад) мНет описания правки |
Irina (обсуждение | вклад) |
||
| (не показано 5 промежуточных версий этого же участника) | |||
| Строка 15: | Строка 15: | ||
представляет собой обход, по которому необходимо идти при перемещении по сети G из точки p в точку q, вместо того чтобы пройти напрямую. Здесь |.| обозначает евклидову длину. ''Геометрическая протяженность сети'' G задается соотношением | представляет собой обход, по которому необходимо идти при перемещении по сети G из точки p в точку q, вместо того чтобы пройти напрямую. Здесь |.| обозначает евклидову длину. ''Геометрическая протяженность сети'' G задается соотношением | ||
(2) <math>\delta(G) := sup_{p \ne q \in G} \delta(p, q)</math>. | (2) <math>\delta(G) := sup_{p \ne q \in G} \; \delta(p, q)</math>. | ||
Это определение отличается от понятия коэффициента растяжения, использовавшегося в контексте остовных деревьев; подробнее об этом – в монографиях Эпштейна [6] или Нарасимхана и Смида [11]. В последней рассматриваются только пути между вершинами <math>p, q \in V \;</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. | ||
Пусть дано конечное множество S точек на плоскости. Требуется найти конечную геометрическую сеть, содержащую S, геометрическая протяженность которой насколько возможно мала. Значение | Пусть дано конечное множество S точек на плоскости. Требуется найти конечную геометрическую сеть, содержащую S, геометрическая протяженность которой насколько возможно мала. Значение | ||
<math>\Delta(S) := inf \{ \delta(G); G \;</math> – конечная плоская геометрическая сеть, содержащая S} | <math>\Delta(S) := inf \{ \delta(G); G \;</math> – конечная плоская геометрическая сеть, содержащая <math>S \} \;</math> | ||
называется ''геометрической протяженностью множества точек'' S. Задача заключается в вычислении или ограничении <math>\Delta(S) \;</math> для данного множества S. | называется ''геометрической протяженностью множества точек'' S. Задача заключается в вычислении или ограничении <math>\Delta(S) \;</math> для данного множества S. | ||
== Основные результаты == | == Основные результаты == | ||
'''Теорема 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>? | ||
== См. также == | == См. также == | ||
