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

'''Лемма 4''' [6]. Пусть G = (V, E) – планарный цивилизованный граф, вложенный в <math>\mathcal{R}^2</math>. Любой эллипс с большой осью c покрывает не более <math>O(c^2)</math> вершин и ребер.

'''Лемма 5''' [5]. Пусть R – выпуклая область в <math>\mathcal{R}^2</math> с площадью A(R) и периметром P(R), и пусть <math>V \subset R</math>. Если у графа единичных дисков для V максимальная степень равна k, то количество вершин в V ограничено соотношением <math>|V| \le 8(k + 1)(A(R) + P(R) + \pi) / \pi</math>.

'''Лемма 6''' [2]. Количество передач, требующееся для построения кучеобразной структуры и системы кластеров для планарного графа G, ограничено <math>O(nD)</math> и <math>O(n^2 D)</math>, соответственно, где n – количество вершин, а D – диаметр G.