Минимальные k-связные геометрические сети: различия между версиями

Теорема 9 ([7]). Пусть d – любое целое число, <math>d \ge 2 \;</math>, а <math>\varepsilon \;</math> – любое положительное вещественное число. Пусть S – множество из n точек в пространстве <math>\mathbb{R}^d \;</math>. Существует рандомизированный алгоритм, который за время <math>n \cdot log \; n \cdot (d / \varepsilon)^{O(d)} + n \cdot 2^{(d / \varepsilon)^{O(d^2)}} + n \cdot 2^{2^{d^{d^{O(1)}}}}</math> с вероятностью не менее 0,99 находит <math>(1 + \varepsilon) \;</math>-аппроксимацию геометрической сети с повышенной живучестью с <math>r_v \in \{ 0, 1, 2 \} \;</math> для любого <math>v \in V \;</math>. Этот алгоритм может быть дерандомизирован за полиномиальное время.