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

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

Пусть A и B – два конечных множества точек в <math>\mathcal{R}^d</math>. Будем называть A и B ''значительно удаленными'' по отношению к вещественному числу s > 0, если существуют два непересекающихся шара <math>C_A \;</math> и <math>C_B \;</math> одного и того же радиуса, такие, что <math>C_A \;</math> содержит A, <math>C_B \;</math> содержит B, а расстояние между <math>C_A \;</math> и <math>C_B \;</math> по меньшей мере в s раз превышает радиус <math>C_A \;</math>. Значение s называется коэффициентом удаления.

'''Определение 1'''. Пусть S – множество точек в пространстве <math>\mathcal{R}^d \;</math>, а s > 0 – вещественное число. ''Декомпозицией значительно удаленных пар'' (well-separated pair decomposition, WSPD) для S относительно s является последовательность <math>\{ A_i, B_i \} , 1 \le i \le m \;</math>, пар непустых подмножеств S, таких, что: