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

Пусть A и B – два конечных множества точек в <math>\mathcal{R}^d</math>. Будем называть A и B ''значительно удаленными'' по отношению к вещественному числу s > 0, если существуют два непересекающихся шара <math>C_A \;</math> и <math>C_B \;</math> одного и того же радиуса, такие, что <math>C_A \;</math> содержит A, <math>C_B \;</math> содержит B, а расстояние между <math>C_A \;</math> и <math>C_B \;</math> по меньшей мере в s раз превышает радиус <math>C_A \;</math>. Значение s называется ''коэффициентом удаления''.

'''Определение 1 [6]'''. Пусть S – множество точек в пространстве <math>\mathcal{R}^d \;</math>, а s > 0 – вещественное число. ''Декомпозицией значительно удаленных пар'' (well-separated pair decomposition, WSPD) для S относительно s является последовательность <math>\{ A_i, B_i \} , 1 \le i \le m \;</math>, пар непустых подмножеств S, таких, что:

Декомпозицию значительно удаленных пар разработали Кэллахан и Косарайю [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.

Для геометрических остовов естественно рассматривать ''отказы областей'' – то есть отказы, уничтожающие все вершины и ребра, пересекающие некоторую нерабочую геометрическую область. Пусть для нерабочей области 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>.

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

Задача построения остовов активно исследовалась с теоретической точки зрения, но получила гораздо меньше внимания с практической, или экспериментальной, стороны. Наварро и Паредес [1] предложили четыре эвристики для множеств точек в пространстве высоких размерностей (d = 20) и эмпирическими методами показали, что время выполнения составило <math>O(n^{2,24}) \;</math>, а количество ребер в полученных графах – <math>O(n^{1,13}) \;</math>. Недавно Фарши и Гудмундссон [12] провели тщательное сравнение алгоритмов построения остовов, упоминавшихся в разделе «Остовы на точках в евклидовом пространстве».