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

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

1. Разработка алгоритма построения динамического t-остова, который можно обновлять за время O(logc n) для некоторого константного значения c.

3. Алгоритм построения k-вершинного отказоустойчивого остова, который предложили Шумай и Чжао [8], позволяет получить k-вершинный отказоустойчивый t-остов степени O(k) с общим весом O(k2 ■ wt(MST(S))). Однако до сих пор неизвестны способы его эффективной реализации. Можно ли вычислить такой остов за время O(nlog n + kn)?

Задача построения остовов активно исследовалась с теоретической точки зрения, но получила гораздо меньше внимания с практической, или экспериментальной, стороны. Наварро и Паредес [ ] предложили четыре эвристики для множеств точек в пространстве высоких размерностей (d = 20) и эмпирическими методами показали, что время выполнения составило O(n2.24), а количество ребер в полученных графах – O(n1.13). Недавно Фарши и Гудмундссон [12] провели тщательное сравнение алгоритмов построения остовов, упоминавшихся в разделе «Остовы на точках в евклидовом пространстве».