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

Системы кластеров [ ]. Пусть G = (V, E) – неориентированный планарный граф, имеющий n = |V| вершин и радиус R. Можно построить систему семейств кластеров F(0), F(1), ..., F(logR), такую, что (1) диаметр каждого кластера в F(i) составляет O(2i log n), (2) каждая вершина принадлежит не более чем к O(log n) кластерам, (3) для любых двух вершин, расстояние между которыми в G описывается неравенством 2' l < d < 2i, существует по меньшей мере один кластер в F(i), содержащий две вершины.

Лемма 1 [9]. Триангуляция Делоне A для множества точек V мощности n может быть построена локально за время O(n log n).

Лемма 2 [4]. Рассмотрим любые s, t 2 V. Предположим, что x и y – две точки, такие, что s, x и y принадлежат к триангуляции Делоне A. Пусть a и f$ - углы, образованные сегментами xs и st, и сегментами ts и sy, соответственно. Если a < f$, то |xs| < |st|. В противном случае |ys| < |st|.

Лемма 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.

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