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

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

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

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