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

'''Теорема 3 ([14]). Приближенный жадный t-остов на множестве S, имеющий максимальную степень <math>O(1/(t - 1)^{2d - 1}) \;</math> и вес <math>O((1 / (t - 1)^{2d - 1} \cdot wt(MST(S))))</math>, может быть построен за время <math>O(n/((t - 1)^{2d}) \; log \; n)</math>.'''

'''Отказоустойчивые остовы'''

Понятие отказоустойчивых остовов было введено Левкопулосом и др. [16] в 1998 году. Оно означает, что при отказе одной или нескольких вершин либо одного или нескольких ребер остов должен сохранить свои основные свойства. В частности, в том, что осталось от остова после отказа вершин или ребер, по-прежнему должен сохраниться короткий путь между любыми двумя вершинами. Шумай и Чжао [8] показали, что жадный подход позволяет получить k-вершинный (или k-реберный) отказоустойчивый геометрический t-остов степени O(k) с общим весом <math>O(k^2 \cdot wt(MST(S))) \;</math>; эти границы являются асимптотически оптимальными.

Для геометрических остовов естественно рассматривать ''отказы областей'' – то есть отказы, уничтожающие все вершины и ребра, пересекающие некоторую нерабочую геометрическую область. Пусть для нерабочей области F граф <math>G \ominus F</math> представляет собой часть G, оставшуюся после того, как точки из S, находящиеся внутри области F, и все ребра, пересекающие F, были удалены из графа; см. рис. 1b. Абам и др. [1] показали, как строить t-остовы размера O(n log n), являющиеся отказоустойчивыми при  отказе любой выпуклой области. Если разрешается использовать [[точка Штейнера|точки Штейнера]], можно получить t-остов линейного размера.

'''Остовы с многоугольными препятствиями'''

'''Динамические и кинетические остовы'''

О динамических или кинетических остовах известно не так уж много. Арья и др. [4] предложили структуру данных размера O(n log n), поддерживающую остов на базе списков с пропусками, описанный выше, с ожидаемым амортизированным временем вставки и удаления <math>O(log^d \; n \; log \; log \; n)</math> на основе модели случайных обновлений.

Гао и др. [13] показали, как поддерживать t-остов размера <math>O(n/(t - 1)^d) \;</math> с максимальной степенью <math>O(1 / (t - 2)^d \; log \; \alpha)</math> и временем вставки и удаления <math>O((log \; \alpha)/(t - 1)^d)</math>, где <math>\alpha \;</math> обозначает пропорциональность S, т.е. отношение максимального расстояния между парой вершин к минимальному. Алгоритм основан на использовании иерархической структуры T с <math>O(log \; \alpha)</math> уровнями, каждый уровень которой содержит множество центров (подмножество S). Каждая вершина v на уровне i в структуре T связана ребрами со всеми остальными вершинами уровня i, находящимися на расстоянии не более <math>O(2^i / (t - 1)) \;</math> от v. Полученный граф является t-остовом S и может поддерживаться вышеописанным образом. Этот подход может быть обобщен до кинетического случая таким образом, чтобы количество событий в процессе поддержки остова составляло <math>O(n^2 \; log \; n)</math> при псевдоалгебраическом характере перемещения. Каждое событие может быть обновлено за время <math>O((log \; \alpha)/(t - 1)^d)</math>.