Маршрутизация в геометрических сетях: различия между версиями

'''Лемма 3'''. Пусть G = (V, E) – планарный граф, вложенный в R2, а s, t 2 V. Далее, обозначим за xi ближайшую к t точку пересечения, определяемую некоторым ребром ei, принадлежащим к некоторой грани Fi, и отрезком прямой st. Аналогично обозначим за xi+1 ближайшую к t точку пересечения, определяемую некоторым ребром, принадлежащим к грани Fi+1, и отрезком прямой st, где грань Fi+1 инцидентна Fi посредством ребра ei. Тогда jxi, t j > jxi+1, tj:

'''Лемма 4''' [6]. Пусть G = (V, E) – планарный цивилизованный граф, вложенный в R2. Любой эллипс с большой осью c покрывает не более O(c2) вершин и ребер.

'''Лемма 5''' [5]. Пусть R – выпуклая область в R2 с площадью A(R) и периметром P(R), и пусть V С R: Если у графа единичных дисков для V максимальная степень равна k, то количество вершин в V ограничено |V| < 8(k + 1)(A(R) + P(R) + n)ln.