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

Иначе говоря, если множество точек S не является одним из этих специальных множеств, то любая плоская сеть, множество вершин которой включает S, имеет протяженность выше некоторой нижней границы 1 + r](S). Доказательство теоремы 1 использует следующее соображение о плотности. Предположим, что каждая пара точек из S соединена отрезком прямой. Обозначим за S0 объединение S и всех получившихся точек пересечения. Применим то же самое построение к S0 и затем повторим процесс. Для множества предельных точек S1 верна следующая теорема. Она обобщает работы Хиллара и Ри [8], а также Исмаилеску и Радойчича [ ], посвященные пересечениям линий.

Теорема 2 ([11]). Если множество S не содержится в одном из множеств вершин, изображенных на рис. 1, то S1 плотно располагается в некоторой многоугольной части плоскости.

Теорема 3 ([4]). Пусть N – бесконечная плоская сеть, все грани которой имеют диаметр, ограниченный сверху некоторой константой. Тогда имеет место соотношение a(N) > 1,00156.

Теорема 4 ([4]). Обозначим за C (бесконечное) множество всех точек на замкнутой выпуклой кривой. Тогда имеет место соотношение Ј{C) > 1,00157.

Теорема 5 ([4]). Пусть дано n семейств Fi; 2 < i < n, каждое из которых состоит из бесконечного числа равноудаленных параллельных прямых. Предположим, что эти семейства находятся в общем положении. Тогда протяженность их графа пересечений G составляет не менее 2/p3.

Теорема 6 ([4]). Каждое конечное множество точек S имеет протяженность E(S) < 1,1247.