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

Множество ориентированных ребер удовлетворяет свойству пробелов, если источники любых двух разных ребер разделены расстоянием, по крайней мере в несколько раз превышающим длины кратчайшего из двух ребер. Арья и Смид [5] предложили алгоритм, использующий свойство пробелов для определения того, может ли некоторое ребро быть добавлено к t-остовному графу. Используя свойство пробелов, можно доказать, что построенный остов имеет степень O{ll9d~l) и вес O(log n • wt(MST(S))), где wt(MST(S)) – вес минимального остовного дерева S.

WSPD-граф

Пусть A и B – два конечных множества точек в Rd. Будем называть A и B значительно удаленными по отношению к вещественному числу s > 0, если существуют два непересекающихся шара CA и CB одного и того же радиуса, такие, что CA содержит A, CB содержит B, а расстояние между CA и CB по меньшей мере в s раз превышает радиус CA. Значение s называется коэффициентом удаления.

Определение 1. Пусть S – множество точек в пространстве Rd, а s > 0 – вещественное число. Декомпозицией значительно удаленных пар (well-separated pair decomposition, WSPD) для S относительно s является последовательность fAi ; Bi g, 1 < i < m, пар непустых подмножеств S, таких, что (1) Ai \ B i = ; для всех i = 1, 2, ... , m; (2) для каждой неориентированной пары {p, q} различных точек S существует ровно одна пара {Ai, Bi} в последовательности, такая, что p 2 Ai и q 2 Bi либо p 2 Bi и q 2 Ai; (3) Ai и Bi являются значительно удаленными относительно s для всех i = 1, 2, ... , m.