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

Теорема 1. <math>\Theta \;</math>-граф представляет собой t-остов на множестве S для <math>t = 1 / (cos \; \theta — sin \; \theta)</math>, имеющий <math>O(n / \theta^{d - 1}) \;</math> ребер, и может быть вычислен за время <math>O((n / \theta^{d - 1}) log^{d - 1} \; n)</math> с использованием <math>O(n / \theta^{d - 1} + n \; log^{d - 2} \; n)</math> памяти.