4551
правка
Геометрические остовы: различия между версиями
Перейти к навигации
Перейти к поиску
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 71: | Строка 71: | ||
Декомпозицию значительно удаленных пар разработали Кэллахан и Косарайю [ ]. Построение t-остова при помощи этого подхода заключается в построении декомпозиции S относительно коэффициента удаления s = (4(t + 1))/(t — 1). Вначале возьмем за остовный граф G = (S; | Декомпозицию значительно удаленных пар разработали Кэллахан и Косарайю [6]. Построение t-остова при помощи этого подхода заключается в построении декомпозиции 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, имеющий O | '''Теорема 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. Арья и др. [ ] предложили алгоритм, сохраняющий только самое короткое ребро для каждого направления конуса, объединив таким образом подход к построению <math>\Theta \;</math>-графа с подходом для WSPD-графа. Добавив шаг постобработки, рассматривающий все вершины с высокой степенью, можно получить t-остов степени O( | Одна и та же точка v может быть частью нескольких значительно удаленных пар, и каждая из этих пар может сгенерировать ребро с конечной точкой в v. Арья и др. [2] предложили алгоритм, сохраняющий только самое короткое ребро для каждого направления конуса, объединив таким образом подход к построению <math>\Theta \;</math>-графа с подходом для WSPD-графа. Добавив шаг постобработки, рассматривающий все вершины с высокой степенью, можно получить t-остов степени <math>O(1 / (t - 1)^{2d - 1}) \;</math>. | ||
Жадный остов | '''Жадный остов''' | ||
Жадный алгоритм был впервые представлен в 1989 году Берном (см. также работу Ленкопулоса и Лингаса [15]) и с тех пор широко исследовался. Граф, построенный при помощи жадного алгоритма, будем называть жадным остовом. Основная идея заключается в итеративном построении графа G. Ребра полного графа обрабатываются в порядке возрастания длины. Проверка ребра (u, v) включает запрос о кратчайшем пути в частичном остовном графе G. Если кратчайший путь в G между u и v не превышает t • | [[Жадный алгоритм]] был впервые представлен в 1989 году Берном (см. также работу Ленкопулоса и Лингаса [15]) и с тех пор широко исследовался. Граф, построенный при помощи жадного алгоритма, будем называть жадным остовом. Основная идея заключается в итеративном построении графа G. Ребра полного графа обрабатываются в порядке возрастания длины. Проверка ребра (u, v) включает запрос о кратчайшем пути в частичном остовном графе G. Если кратчайший путь в G между u и v не превышает t • |uv|, то ребро (u, v) отбрасывается, в противном случае оно добавляется к частичному остовному графу G. | ||
Дас, Нарасимхан и Салоу [ ] доказали, что жадный остов удовлетворяет так называемому | Дас, Нарасимхан и Салоу [ ] доказали, что жадный остов удовлетворяет так называемому ''свойству прыжков''. Множество неориентированных ребер E удовлетворяет свойству t-прыжков, если для любого <math>k \ge 2 \;</math> и любой возможной последовательности f(p1; q1)..: ; (pk; qk)g попарно различающихся ребер E, | ||