Геометрические остовы: различия между версиями

Множество ориентированных ребер удовлетворяет свойству пробелов, если источники любых двух разных ребер разделены расстоянием, по крайней мере в несколько раз превышающим длины кратчайшего из двух ребер. Арья и Смид [5] предложили алгоритм, использующий свойство пробелов для определения того, может ли некоторое ребро быть добавлено к t-остовному графу. Используя свойство пробелов, можно доказать, что построенный остов имеет степень <math>O (1 / \theta^{d - 1}) \;</math> и вес O(log n • wt(MST(S))), где wt(MST(S)) – вес минимального остовного дерева S.