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

Перейти к навигации Перейти к поиску
м
Строка 71: Строка 71:




Декомпозицию значительно удаленных пар разработали Кэллахан и Косарайю [6]. Построение t-остова при помощи этого подхода заключается в построении декомпозиции S относительно коэффициента удаления s = (4(t + 1))/(t 1). Вначале возьмем за остовный граф <math>G = (S, \empty) \;</math> и будем итеративно добавлять ребра следующим образом. Для каждой значительно удаленной пары {A, B} из декомпозиции к графу добавляется ребро (a, b), где a и b – произвольные точки из A и B, соответственно. Полученный граф называется WSPD-графом на S.
Декомпозицию значительно удаленных пар разработали Кэллахан и Косарайю [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.




'''Теорема 2. WSPD-граф представляет собой t-остов на множестве S, имеющий <math>O(s^d \cdot n) \;</math> ребер, и может быть построен за время <math>O(s^dn + n \; log \; n)</math>, где s = 4(t + 1)/(t 1).'''
'''Теорема 2. WSPD-граф представляет собой t-остов на множестве S, имеющий <math>O(s^d \cdot n) \;</math> ребер, и может быть построен за время <math>O(s^dn + n \; log \; n)</math>, где s = 4(t + 1)/(t - 1).'''




Строка 80: Строка 80:




'''Ограниченный диаметр'''
'''Граф с ограниченным диаметром'''


Арья, Маунт и Смид [3] предложили модификацию алгоритма построения, в результате которой диаметр графа оказывается ограничен 2 log n. Вместо выбора произвольной точки в каждом значительно удаленном множестве их алгоритм тщательно выбирает особую точку для каждого множества.
Арья, Маунт и Смид [3] предложили модификацию алгоритма построения, в результате которой диаметр графа оказывается ограничен 2 log n. Вместо выбора произвольной точки в каждом значительно удаленном множестве их алгоритм тщательно выбирает особую точку для каждого множества.




'''Ограниченная степень'''
'''Граф с ограниченной степенью'''


Одна и та же точка v может быть частью нескольких значительно удаленных пар, и каждая из этих пар может сгенерировать ребро с конечной точкой в v. Арья и др. [2] предложили алгоритм, сохраняющий только самое короткое ребро для каждого направления конуса, объединив таким образом подход к построению <math>\Theta \;</math>-графа с подходом для WSPD-графа. Добавив шаг постобработки, рассматривающий все вершины с высокой степенью, можно получить t-остов степени <math>O(1 / (t - 1)^{2d - 1}) \;</math>.
Одна и та же точка v может быть частью нескольких значительно удаленных пар, и каждая из этих пар может сгенерировать ребро с конечной точкой в v. Арья и др. [2] предложили алгоритм, сохраняющий только самое короткое ребро для каждого направления конуса, объединив таким образом подход к построению <math>\Theta \;</math>-графа с подходом для WSPD-графа. Добавив шаг постобработки, рассматривающий все вершины с высокой степенью, можно получить t-остов степени <math>O(1 / (t - 1)^{2d - 1}) \;</math>.
4551

правка

Навигация