4446
правок
Геометрическая протяженность геометрических сетей: различия между версиями
Материал из WEGA
Геометрическая протяженность геометрических сетей (посмотреть исходный код)
Версия от 21:55, 19 января 2018
, 19 января 2018→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 67: | Строка 67: | ||
Следующий результат задает верхнюю и нижнюю границы A(S). | |||
'''Теорема 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]. | |||
[[Файл:GDGN_3.png]] | |||
Рисунок 3. Сеть с геометрической протяженностью, приблизительно равной 1,6778 | |||
Теорема 4 [3]. Существует конечное множество точек S, такое, что | '''Теорема 4 [3]. Существует конечное множество точек S, такое, что <math>\Delta(S) > (1 + 10^{-11}) \; \pi / 2</math>.''' | ||
Теорема 4 выполняется для множества точек S размером 19 x 19 вершин целочисленной решетки. Грубо говоря, если S заключено в геометрическую сеть G с протяженностью, близкой к | Теорема 4 выполняется для множества точек S размером 19 x 19 вершин целочисленной решетки. Грубо говоря, если S заключено в геометрическую сеть G с протяженностью, близкой к <math>\pi / 2 \;</math>, то, согласно лемме 3, границы граней G должны быть заключены в небольшом кольце. Для получения внутреннего и внешнего кругов этого кольца следует воспользоваться утверждением Купербергов и др. [9], гласящим, что расширение упаковки дисков радиуса <math>\le 1 \;</math> на определенный коэффициент не может покрыть квадрат со стороной 4. | ||
== Применение == | == Применение == | ||
