4430
правок
Геометрические остовы: различия между версиями
Материал из WEGA
м
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 71: | Строка 71: | ||
Декомпозицию значительно удаленных пар разработали Кэллахан и Косарайю [6]. Построение t-остова при помощи этого подхода | Декомпозицию значительно удаленных пар разработали Кэллахан и Косарайю [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 | '''Теорема 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>. | ||
