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

'''Лемма 2''' [4]. Рассмотрим любые <math>s, t \in V</math>. Предположим, что x и y – две точки, такие, что s, x и y принадлежат к триангуляции Делоне <math>\Delta</math>. Пусть <math>\alpha</math> и <math>\beta</math> - углы, образованные сегментами <math>\bar{xs}</math> и <math>\bar{st}</math>, и сегментами <math>\bar{ts}</math> и <math>\bar{sy}</math>, соответственно. Если <math>\alpha < \beta</math>, то |xs| < |st|. В противном случае |ys| < |st|.

'''Лемма 3'''. Пусть G = (V, E) – планарный граф, вложенный в <math>\mathcal{R}^2</math> и <math>s, t \in V</math>. Далее, обозначим за <math>x_i</math> ближайшую к t точку пересечения, определяемую некоторым ребром <math>e_i</math>, принадлежащим к некоторой грани <math>F_i</math>, и отрезком прямой <math>\bar{st}</math>. Аналогично обозначим за <math>x_{i + 1}</math> ближайшую к t точку пересечения, определяемую некоторым ребром, принадлежащим к грани <math>F_{i + 1}</math>, и отрезком прямой <math>\bar{st}</math>, где грань <math>F_{i+1}</math> инцидентна <math>F_i</math> посредством ребра <math>e_i</math>. Тогда <math>x_i, t| > |x_{i+1}, t|</math>.

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