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

Гао и др. [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>.

Алгоритмы построения разреженных остовов получили широкое применение в таких областях, как поиск в метрическом пространстве [1], который включает запрос по содержанию в мультимедийных объектах, текстовый информационный поиск, распознавание образов и аппроксимацию функций. Еще одним примером является широковещательная рассылка в сетях коммуникаций [17]. Несколько хорошо известных теоретических работ также основываются на построении t-остовов – к примеру, Рао и Смит [19] совершили прорыв, предложив схему аппроксимации с оптимальным временем O(nlog n) для хорошо известной [[Евклидова задача коммивояжера|евклидовой задачи коммивояжера]] с использованием t-остовов (или баньянов). А Шумай и Лингас [7] предложили схемы аппроксимации для задач о многосвязности с нахождением объектов минимальной стоимости в геометрических сетях.