Протяженность геометрических сетей: различия между версиями

Если разрешены пересечения ребер, можно использовать остовы, протяженность которых может быть сделана произвольно близкой к 1; подробнее см. в монографиях Эпштейна [6] либо Нарасимхана и Смида [12]. Известны различные типы триангуляций S с коэффициентами растяжения, ограниченными сверху небольшими константами, среди которых стоит упомянуть триангуляцию Делоне с коэффициентом растяжения, не превышающим 2,42; см. Добкин и др. [3], Кил и Гутвин [10], Дас и Джозеф [2]. Эпштейн [5] дал характеристику всех триангуляций T протяженностью <math>\sigma(T) = 1 \;</math>; эти триангуляции представлены на рис. 1. Очевидно, <math>\Sigma(S) = 1 \;</math> выполняется для любого множества точек S, содержащегося в множестве вершин подобной триангуляции T.

Иначе говоря, если множество точек S не является одним из этих специальных множеств, то любая плоская сеть, множество вершин которой включает S, имеет протяженность выше некоторой нижней границы <math>1 + \eta(S) \;</math>. Доказательство теоремы 1 использует следующее соображение о плотности. Предположим, что каждая пара точек из S соединена отрезком прямой. Обозначим за S' объединение S и всех получившихся точек пересечения. Применим то же самое построение к S' и затем повторим процесс. Для множества предельных точек <math>S^\infty \;</math> верна следующая теорема. Она обобщает работы Хиллара и Ри [8], а также Исмаилеску и Радойчича [9], посвященные пересечениям прямых.

Для практического применения в дополнение к верхним границам протяженности пригодились бы верхние границы веса (т.е. общей длины ребер) геометрической сети. Некоторые теоретические вопросы также требуют дополнительного исследования. Всегда ли <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>?

Рис. 3. Наилучшее известное вложение для <math>S_5 \;</math>