Применение геометрических остовных сетей: различия между версиями

'''Теорема 1. Пусть t > 1 и <math>\varepsilon ' > 0 \;</math> – вещественные константы. Пусть S – множество из n точек в пространстве <math>\mathbb{R}^d \;</math>, а G = (S, E) – t-остов для S, имеющий m ребер. Существует алгоритм, за время O(m + nlog n) вычисляющий <math>(1 + \varepsilon ') \; </math>-остов G, имеющий O(n) ребер и вес O(wt(MST(S))).'''

'''Теорема 2. Пусть S – множество из n точек в пространстве <math>\mathbb{R}^d \;</math>, а <math>c \ge 7 \;</math> – целочисленная константа. За время O(n log n) можно вычислить структуру данных D(S), в которую входят:

1. последовательность <math>L_1, L_2, ..., L_{\ell} \;</math> вещественных чисел, где <math>\ell = O(n) \;</math>, и

2. последовательность <math>S_1, S_2, ..., S_{\ell} \;</math> подмножеств S, удовлетворяющих соотношению <math>\sum_{i = 1}^{\ell} |S_i| = O(n) \;</math>,

для любых двух различных точек p и q в множестве S возможно за время O(1) вычислить индекс i, <math>1 \le i \le \ell \;</math>, и две точки x и y в множестве <math>S_i \;</math>, такие, что (1) <math>L_i / n^{c + 1} \le |xy| < L_i \;</math>; (2) и |px|, и |qy| меньше <math>|xy| / n^{c - 2} \;</math>.'''