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

'''Триангуляция Делоне''' <math>\Delta</math> множества вершин V, вложенных в <math>\mathcal{R}^2</math>, представляет собой геометрическую двойственную конструкцию диаграммы Вороного [9] V, в которой две вершины в V связаны ребром в <math>\Delta</math>, если соответствующие им ячейки диаграммы Вороного инцидентны друг другу. Триангуляция Делоне <math>\Delta</math> является ''единичной'', если длина ребер в ней не превышает 1.

«'''Принцип правой руки'''»: правило, используемое алгоритмами обхода графа, которые при движении в выбранную сторону первым выбирают ребро, ведущее направо.

'''Кучеобразная структура'''. Пусть G = (V, E) – неориентированный планарный граф, такой, что каждая вершина в V содержит некоторое численное значение. Кучеобразная структура представляет собой базисное возможное решение (BFS) в виде дерева T, содержащее все вершины G, такое, что для каждой вершины v, отличной от корня, хранящееся в v значение меньше значения, хранящегося в предке v.

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