4551
правка
Геометрические остовы: различия между версиями
Перейти к навигации
Перейти к поиску
м
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 62: | Строка 62: | ||
'''Определение 1 [6]'''. Пусть S – множество точек в пространстве <math>\mathcal{R}^d \;</math>, а s > 0 – вещественное число. ''Декомпозицией значительно | '''Определение 1 [6]'''. Пусть 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) <math>A_i \cap B_i = \empty \;</math> для всех i = 1, 2, ... , m; | (1) <math>A_i \cap B_i = \empty \;</math> для всех i = 1, 2, ... , m; | ||
| Строка 71: | Строка 71: | ||
Декомпозицию значительно | Декомпозицию на значительно удаленные пары разработали Кэллахан и Косарайю [6]. Построение t-остова при помощи этого подхода начинается с построения WSPD-декомпозиции S относительно коэффициента удаления s = (4(t + 1))/(t - 1). Вначале положим остовный граф равным <math>G = (S, \empty) \;</math> и будем итеративно добавлять ребра следующим образом. Для каждой значительно удаленной пары {A, B} из декомпозиции к графу добавляется ребро (a, b), где a и b – произвольные точки из A и B, соответственно. Полученный граф называется WSPD-графом на S. | ||