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

'''Теорема 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>.'''