4846
правок
Протяженность геометрических сетей: различия между версиями
Перейти к навигации
Перейти к поиску
м
Протяженность геометрических сетей (посмотреть исходный код)
Версия от 03:22, 20 февраля 2018
, 20 февраля 2018→Открытые вопросы
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| (не показано 5 промежуточных версий этого же участника) | |||
| Строка 10: | Строка 10: | ||
(1) <math>\sigma (p,q) := \frac{| \xi_G (p,q) |}{|pq|}</math> | (1) <math>\sigma (p,q) := \frac{| \xi_G (p,q) |}{|pq|}</math> | ||
представляет собой обход, по которому необходимо идти при перемещении по сети G из точки p в точку q, вместо того чтобы пройти напрямую. Здесь |.| обозначает евклидову длину. Протяженность сети G задается следующим образом: | представляет собой обход, по которому необходимо идти при перемещении по сети G из точки p в точку q, вместо того чтобы пройти напрямую. Здесь |.| обозначает евклидову длину. | ||
''Протяженность'' сети G задается следующим образом: | |||
(2) <math>\sigma(G) := max_{p \ne q \in V} \; \sigma(p, q)</math> | (2) <math>\sigma(G) := max_{p \ne q \in V} \; \sigma(p, q)</math> | ||
| Строка 18: | Строка 21: | ||
Пусть дано конечное множество S точек на плоскости. Требуется найти плоскую геометрическую сеть G = (V, E) | Пусть дано конечное множество S точек на плоскости. Требуется найти плоскую геометрическую сеть G = (V, E) с насколько возможно малой протяженностью <math>\sigma(G) \;</math>, такую, что S содержится в V. Значение | ||
<math>\Sigma(S) := inf \{ \sigma(G); G = (V, E) \;</math> – конечная плоская геометрическая сеть, | <math>\Sigma(S) := inf \{ \sigma(G); G = (V, E) \;</math> – конечная плоская геометрическая сеть, где <math>S \subset V \} \;</math> | ||
называется протяженностью множества точек S. Задача заключается в вычислении или ограничении <math>\Sigma(S) \;</math> для данного множества S. | называется ''протяженностью множества точек'' S. Задача заключается в вычислении или ограничении <math>\Sigma(S) \;</math> для данного множества S. | ||
== Родственные работы == | |||
Если разрешены пересечения ребер, можно использовать остовы, протяженность которых может быть сделана произвольно близкой к 1; подробнее см. в монографиях Эпштейна [6] либо Нарасимхана и Смида [12]. Известны различные типы триангуляций S с коэффициентами растяжения, ограниченными сверху небольшими константами, среди которых стоит упомянуть триангуляцию Делоне с коэффициентом растяжения, не превышающим 2,42; см. Добкин и др. [3], Кил и Гутвин [10], Дас и Джозеф [2]. Эпштейн [5] дал характеристику всех триангуляций T протяженностью <math>\sigma(T) = 1 \;</math>; эти триангуляции представлены на рис. 1. Очевидно, <math>\Sigma(S) = 1 \;</math> выполняется для любого множества точек S, содержащегося в множестве вершин подобной триангуляции T. | |||
[[Файл:DGN_1.png]] | |||
Рис. 1. Триангуляции протяженности 1 | |||
== Основные результаты == | == Основные результаты == | ||
| Строка 36: | Строка 40: | ||
'''Теорема 1 ([11]). Если множество S не содержится в одном из множеств вершин, изображенных на рис. 1, то <math>\Sigma(S) > 1 \;</math>.''' | '''Теорема 1 ([11]). Если множество S не содержится в одном из множеств вершин, изображенных на рис. 1, то <math>\Sigma(S) > 1 \;</math>.''' | ||
Иначе говоря, если множество точек S не является одним из этих специальных множеств, то любая плоская сеть, множество вершин которой включает S, имеет протяженность выше некоторой нижней границы <math>1 + \eta(S) \;</math>. Доказательство теоремы 1 использует следующее соображение о плотности. Предположим, что каждая пара точек из S соединена отрезком прямой. Обозначим за | Иначе говоря, если множество точек S не является одним из этих специальных множеств, то любая плоская сеть, множество вершин которой включает S, имеет протяженность выше некоторой нижней границы <math>1 + \eta(S) \;</math>. Доказательство теоремы 1 использует следующее соображение о плотности. Предположим, что каждая пара точек из S соединена отрезком прямой. Обозначим за S' объединение S и всех получившихся точек пересечения. Применим то же самое построение к S' и затем повторим процесс. Для множества предельных точек <math>S^\infty \;</math> верна следующая теорема. Она обобщает работы Хиллара и Ри [8], а также Исмаилеску и Радойчича [9], посвященные пересечениям прямых. | ||
| Строка 46: | Строка 50: | ||
'''Теорема 3 ([4]). Пусть N – бесконечная плоская сеть, все грани которой имеют диаметр, ограниченный сверху некоторой константой. Тогда имеет место соотношение <math>\sigma(N) > 1,00156 \;</math>.''' | '''Теорема 3 ([4]). Пусть N – бесконечная плоская сеть, все грани которой имеют диаметр, ограниченный сверху некоторой константой. Тогда имеет место соотношение <math>\sigma(N) > 1,00156 \;</math>.''' | ||
| Строка 70: | Строка 68: | ||
Для доказательства этой верхней границы встроим любое заданное конечное множество точек S в множество вершин масштабированной и слегка деформированной конечной части сети, представленной на рис. 2. Ее можно получить из упаковки равносторонних треугольников в результате замены каждой вершины маленьким треугольником и соединения соседних треугольников указанным образом. | Для доказательства этой верхней границы встроим любое заданное конечное множество точек S в множество вершин масштабированной и слегка деформированной конечной части сети, представленной на рис. 2. Ее можно получить из упаковки равносторонних треугольников в результате замены каждой вершины маленьким треугольником и соединения соседних треугольников указанным образом. | ||
[[Файл:DGN_2.png]] | |||
Рис. 2. Сеть протяженностью ~ 1,1247 | |||
== Применение == | == Применение == | ||
| Строка 78: | Строка 81: | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Для практического применения в дополнение к верхним границам протяженности пригодились бы верхние границы веса (т.е. общей длины ребер) геометрической сети. Некоторые теоретические вопросы также требуют дополнительного исследования. Всегда ли <math>\Sigma(S) \;</math> достигается для конечной сети? Как вычислить (точно или приближенно) <math>\Sigma(S) \;</math> для заданного конечного множества S? Даже для такого простого множества, как <math>S_5 \;</math>, представляющего собой углы правильного пятиугольника, протяженность неизвестна. Наименьшее известное значение протяженности для триангуляции, среди вершин которой содержится <math>S_5 \;</math> | Для практического применения в дополнение к верхним границам протяженности пригодились бы верхние границы веса (т.е. общей длины ребер) геометрической сети. Некоторые теоретические вопросы также требуют дополнительного исследования. Всегда ли <math>\Sigma(S) \;</math> достигается для конечной сети? Как вычислить (точно или приближенно) <math>\Sigma(S) \;</math> для заданного конечного множества S? Даже для такого простого множества, как <math>S_5 \;</math>, представляющего собой углы правильного пятиугольника, протяженность неизвестна. Наименьшее известное значение протяженности – для триангуляции, среди вершин которой содержится <math>S_5 \;</math> – равно 1,0204 (см. рис. 3). Наконец, чему равно точное значение <math> sup \{ \Sigma(S); S \; finite \}</math>? | ||
[[Файл:DGN_3.png]] | |||
Рис. 3. Наилучшее известное вложение для <math>S_5 \;</math> | |||
== См. также == | == См. также == | ||