4446
правок
Геометрические остовы: различия между версиями
Материал из WEGA
м
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 54: | Строка 54: | ||
'''Жадный подход с пробелами''' | '''Жадный подход с пробелами''' | ||
Множество ориентированных ребер удовлетворяет свойству пробелов, если источники любых двух разных ребер разделены расстоянием, по крайней мере в несколько раз превышающим длины кратчайшего из двух ребер. Арья и Смид [5] предложили алгоритм, использующий свойство пробелов для определения того, может ли некоторое ребро быть добавлено к t-остовному графу. Используя свойство пробелов, можно доказать, что построенный остов имеет степень O{ | Множество ориентированных ребер удовлетворяет свойству пробелов, если источники любых двух разных ребер разделены расстоянием, по крайней мере в несколько раз превышающим длины кратчайшего из двух ребер. Арья и Смид [5] предложили алгоритм, использующий свойство пробелов для определения того, может ли некоторое ребро быть добавлено к t-остовному графу. Используя свойство пробелов, можно доказать, что построенный остов имеет степень <math>O (1 / \theta^{d - 1}) \;</math> и вес O(log n • wt(MST(S))), где wt(MST(S)) – вес минимального остовного дерева S. | ||
WSPD-граф | '''WSPD-граф''' | ||
Пусть A и B – два конечных множества точек в | Пусть 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 – множество точек в пространстве | '''Определение 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, таких, что (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. | ||
