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

В геометрических сетях точки встроены в евклидову плоскость. Каждая вершина осведомлена о своем географическом положении, т. е. знает свои координаты (x, y) на плоскости.

Планарный граф. Граф G = (V, E) является планарным, если вершины V могут быть встроены в двумерное евклидово пространство R2, т. е. каждая вершина из V получает уникальные координаты, а ребра между каждой парой вершин из E изображаются таким образом, что они не пересекают друг друга в R2.

Граф единичных дисков (Unit-Disk Graph, UDG) определяется как граф G = (V, E), встроенный в R2, в котором две вершины u, v 2 V соединены ребром (u, v) 2 E в том случае, если евклидово расстояние между ними, обозначаемое как |u, v|, не превышает 1.

Модель с A-точностью /£?(1) или «цивилизованный граф» – это граф G = (V, E), встроенный в пространство R2, у которого для любого фиксированного A > 0 две вершины u, v 2 V находятся на расстоянии не менее A.

Граф Гэбриэла (Gabriel Graph, G G) определяется как граф G = (V, E), встроенный в R2, в котором для любых u, v 2 V ребро (u, v) 2 E в случае, если u и v – единственные вершины в V, принадлежащие к кругу диаметром (u, v) as diameter.

Триангуляция Делоне Л множества вершин V, встроенных в R2, представляет собой геометрическую двойственную конструкцию для диаграммы Вороного [9] V, в которой две вершины в V связаны ребром в A, если соответствующие им ячейки диаграммы Вороного инцидентны друг другу. Триангуляция Делоне A является единичной, если длина ребер в ней не превышает 1.

Лемма 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) вершин и ребер.