Минимальные геометрические остовные деревья

Ключевые слова и синонимы

Остовные деревья минимальной длины; остовные деревья минимального веса; минимальные евклидовы остовные деревья; MST; EMST

Постановка задачи

Пусть S – множество из n точек в d-мерном вещественном пространстве, где [math]\displaystyle{ d \ge 1 \; }[/math] – целочисленная константа. Минимальное остовное дерево (MST) графа S представляет собой связный ациклический граф с множеством вершин S и минимальной суммарной длиной ребер. Длина ребра равна расстоянию между его конечными точками согласно некоторой метрике. В метрике [math]\displaystyle{ L_p \; }[/math] расстояние между двумя точками x и y с координатами [math]\displaystyle{ (x_1, x_2, ..., x_d) \; }[/math] и [math]\displaystyle{ (y_1, y_2, ..., yd_) \; }[/math], соответственно, определяется как p-й корень суммы [math]\displaystyle{ \sum^d_{i=1} |x_i - y_i|^p \; }[/math].

Основные результаты

Минимальным геометрическим остовным деревьям посвящено множество работ.

В евклидовой метрике L2, где расстояния измеряются по прямой, задача MST в двух измерениях может быть оптимально решена за время O(n log n) с использованием того факта, что MST представляет собой подграф триангуляции Делоне на множестве входных вершин. Последний, в свою очередь, взаимно однозначно соответствует диаграмме Вороного для графа S, для нахождения которой разработано несколько алгоритмов с временем исполнения O(n log n). Термин «оптимально» относится к модели алгебраического дерева вычислений. После вычисления триангуляции Делоне вычисление дерева MST можно произвести всего за O(n) дополнительного времени при помощи алгоритма Черитона-Тарьяна [5].

Даже для более высоких размерностей, т.е. при d > 2, MST представляет собой подграф двойственной диаграммы Вороного; однако этот факт нельзя использовать тем же способом, как в случае двух измерений, поскольку эта двойственная диаграмма может содержать [math]\displaystyle{ \Omega (n^2) \; }[/math] ребер. Следовательно, в случае более высоких размерностей для сокращения количества рассматриваемых ребер нужно использовать другие геометрические свойства. Первый алгоритм для высоких размерностей с временем исполнения ниже квадратичного был предложен Яо [14]. Более эффективный алгоритм позднее предложили Агарвал и коллеги [1]. Для случая [math]\displaystyle{ d = 3 \; }[/math] их алгоритм выполняется за рандомизированное ожидаемое время [math]\displaystyle{ O((n \; log n)^{4/3}) \; }[/math], а для [math]\displaystyle{ d \ge 4 \; }[/math] – за ожидаемое время [math]\displaystyle{ O(n^{2-2/( \left \lceil d/2 \right \rceil + 1) + \epsilon } ) \; }[/math], где [math]\displaystyle{ \epsilon \; }[/math] – произвольно малая положительная константа.

Алгоритм Агарвала и коллег базируется на исследовании отношений между вычислением MST и нахождением ближайшей пары среди n красных точек и m синих точек (вторая задача носит название задачи нахождения бихроматической пары ближайших точек). Они показали, что если обозначить за [math]\displaystyle{ T_d(n, m) \; }[/math] время, необходимое для решения второй задачи, то задача MST может быть решена за время [math]\displaystyle{ O(T_d (n, n)log^d n) \; }[/math]. Позднее Кэллахан и Косарайю [4] улучшили это время до [math]\displaystyle{ O(T_d (n, n) log \; n) }[/math]. Оба метода демонстрируют время исполнения [math]\displaystyle{ O(T_d (n, n)) \; }[/math], если [math]\displaystyle{ T_d(n, n) = \Omega (n^{l + \alpha}) \; }[/math] для некоторого [math]\displaystyle{ \alpha \gt 0 \; }[/math]. Наконец, Кржнарик и коллеги [10] показали, что эти две задачи (нахождение MST и вычисление бихроматической пары ближайших точек) имеют одну и ту же временную сложность в наихудшем случае, с поправкой на константный множитель, в рамках наиболее часто используемой модели алгебраического дерева вычислений и для любой фиксированной [math]\displaystyle{ L_p }[/math]-метрики. Сложнее всего доказать, что задача MST может быть решена за время [math]\displaystyle{ O(T_d(n, n)) \; }[/math]. Второй аспект проблемы – доказательство того, что найти бихроматическую пару ближайших точек не сложнее, чем вычислить MST – намного проще: если вначале вычислить MST для объединения n + m синих и красных точек, после этого найти ближайшую бихроматическую пару можно за линейное время, поскольку по меньшей мере одна такая пара должна быть соединена некоторым ребром MST.

Алгоритм, который предложили Кржнарик и коллеги [10], основан на стандартном способе объединения деревьев в лес при помощи кратчайшей дуги, соединяющей отдельные деревья, сходном с классическими алгоритмами Крускала и Прима для вычисления MST для графов. Для снижения количества кандидатов, которые могут рассматриваться как ребра MST, алгоритм работает в несколько последовательных фаз, на каждой из которых рассматриваются только ребра равной или близкой длины (с коэффициентом не более 2).

Изначальный лес представляет собой множество из S точек; иначе говоря, каждая входная точка считается отдельным деревом, не имеющим ребер. После этого, до тех пор, пока в лесу остается более одного дерева, два дерева сливаются вместе, при этом создается ребро, соединяющее две вершины – по одной из каждого дерева. По окончании этой процедуры ребра образуют единственное дерево, оставшееся в лесу, которое и является выходным значением алгоритма.

Предположим, что следующее ребро, которое собирается создать алгоритм, имеет длину l. Каждое дерево T в лесу подразделяется на группы вершин, каждую из которых представляет одна конкретная вершина. Вершина-представитель такой группы называется ее лидером. Далее, каждая вершина в группе, включая лидера, обладает следующим свойством: она находится от лидера на расстоянии не более [math]\displaystyle{ \epsilon \cdot l \; }[/math], где [math]\displaystyle{ \epsilon \; }[/math] – вещественная константа, близкая к нулю.

Вместо рассмотрения всех пар вершин, которые могли бы быть кандидатами на создание следующего ребра, вначале рассматриваются все пары лидеров. Только в случае, если пара лидеров принадлежит к разным деревьям и расстояние между ними приблизительно равно l, ближайшая пара точек между их соответствующими группами вычисляется при помощи алгоритма нахождения бихроматической пары ближайших точек. Также соблюдается следующий инвариант: для любой фазы алгоритма, создающей ребра длины 0(l), и для любого лидера существует только константное число других лидеров, находящихся от него на расстоянии 0(7). Таким образом, общее количество подлежащих рассмотрению пар лидеров не более чем линейно относительно количества лидеров.

Ближайших лидеров для любого заданного лидера можно эффективно найти при помощи техники группировки и структур данных для динамического опроса ближайших пар[ ], а также дополнительных фиктивных точек, которые можно вставлять и удалять в исследовательских целях в различных небольших блоках на расстоянии O(l) от лидера. Для сохранения инварианта при переходе к последующим фазам количество лидеров соответствующим образом сокращается, по мере того как пары близлежащих групп объединяются в единые группы. Для рассмотрения правильных типов пар также необходимо организовывать группы в зависимости от различных направлений, на которых могут найтись новые кандидаты – ребра MST, смежные с вершинами группы. Подробнее об этом в работе Кржнарика и коллег [10].

Существует специальная версия алгоритма нахождения бихроматической пары ближайших точек, для которой Кржнарик и коллеги [10] показали, что она имеет ту же временную сложность, что и вычисление MST – она работает для специального случая, когда оба множества красных и синих точек имеют очень небольшой диаметр по сравнению с расстоянием между ближайшей бихроматической парой точек. Это соотношение может быть сделано произвольно малым за счет выбора подходящего значения " в качестве параметра для создания групп и лидеров. Этот факт использовался для выведения более эффективных алгоритмов для трехмерного случая.

К примеру, в метрике L1 возможно за время O(n log n) построить специальную разновидность планарной диаграммы Вороного для синих точек на плоскости, отделяющей синие точки от красных и имеющей следующее свойство: для каждой рассматриваемой точки q в полупространстве, включающем красные точки, можно использовать эту диаграмму Вороного, чтобы за время O(log n) найти синюю точку, ближайшую к q согласно метрике L1. (Можно рассматривать эту планарную диаграмму Вороного как определяемую вертикальными проекциями синих точек на плоскость, содержащую диаграмму, а размер клетки Вороного зависит от расстояния между соответствующей синей точкой и плоскостью). Таким образом, рассматривая последовательно каждую красную точку, можно решить задачу нахождения бихроматической пары ближайших точек для подобных сильно разнесенных красно-синих множеств за полное время O(nlog n).

Используя этот подход, Кржнарик и коллеги [10] показали, как вычислить MST для S за оптимальное время O(n log n) согласно метрикам L1 и L1 в случае, если d = 3. Время исполнения было улучшено по сравнению с ранее известными границами благодаря работам Габова и коллег [9] и Беспамятных [ ], которые доказали, что для d = 3 MST можно вычислить за время O(n log n log log n) согласно метрикам L1 и L1. Основные результаты Кржнарика и коллег [ ] можно изложить в следующей теореме.

Теорема. В модели алгебраического дерева вычислений для любой фиксированной Lp-метрики и любого фиксированного количества размерностей вычисление MST имеет ту же временную сложность в наихудшем случае, с поправкой на константный множитель, что и вычисление бихроматической пары ближайших точек. Кроме того, в трехмерном пространстве с метриками L1 и L1 задача MST, также как и вычисление бихроматической пары ближайших точек, требуют оптимального времени вычисления O(n log n).

Приближенные и динамические решения

Кэллахан и Косарайю [ ] показали, что остовное дерево, длина которого отличается от длины MST не более чем на множитель 1 + e, может быть вычислено за время O (n (log n + e ~d/2 log e ~ 1)). Алгоритмы аппроксимации с менее оптимальным соотношением времени и качества ранее предложили Кларксон [6], Вайдья [13] и Салоу [12]. Кроме того, если исходный набор точек поддерживается определенными базовыми структурами данных, то приблизительная длина MST может быть вычислена за рандомизированное сублинейное время [ ]. Эпштейн [ ] предложил полностью динамические алгоритмы, сохраняющие MST при вставке или удалении точек.

Применение

Минимальные остовные деревья (MST) входят в число самых базовых структур в таких дисциплинах, как вычислительная геометрия и теория графов, и имеют множество вариантов применения.

Открытые вопросы

Поскольку сложность вычисления MST связана со сложностью нахождения бихроматических пар ближайших точек, открытые вопросы в этих двух задачах родственны; к ним относятся, например, такие варианты, как работа с числом размерностей выше 3.

Экспериментальные результаты

Нарасимхан и Захариасен [ ] провели эксперименты с вычислением минимальных геометрических остовных деревьев при помощи декомпозиции значительно удаленных пар.

См. также

• Деревья с ограниченной степенью
• Полностью динамические минимальные остовные деревья
• Жадные алгоритмы покрытия множества
• Максимальное листовое остовное дерево
• Минимальные остовные деревья
• Параллельная связность и минимальные остовные деревья
• Рандомизированное минимальное остовное дерево
• Прямолинейное остовное дерево
• Прямолинейное дерево Штейнера
• Лес Штейнера
• Деревья Штейнера

Литература

1. Agarwal, P.K., Edelsbrunner, H., Schwarzkopf, O., Welzl, E.: Euclidean minimum spanning trees and bichromatic closest pairs. Discret.Comput. Geom. 6,407-422 (1991)

2. Bespamyatnikh, S.: On Constructing Minimum Spanning Trees in Rk1.Algorithmica 18(4), 524-529 (1997)

3. Bespamyatnikh, S.: An Optimal Algorithm for Closest-Pair Maintenance. Discret. Comput. Geom. 19(2), 175-195 (1998)

4. Callahan, P.B., Kosaraju, S.R.: Faster Algorithms for Some Geometric Graph Problems in Higher Dimensions. In: SODA 1993, pp.291-300

5. Cheriton, D.and Tarjan, R.E.: Finding Minimum Spanning Trees. SIAM J. Comput. 5(4), 724-742 (1976)

6. Clarkson, K.L.: Fast Expected-Time and Approximation Algorithms for Geometric Minimum Spanning Trees. In: Proc. STOC 1984, pp. 342-348

7. Czumaj, A., ErgCin,F., Fortnow, L., Magen,A., Newman, I., Rubinfeld, R., Sohler, C.: Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time. SIAM J. Comput. 35(1),91-109(2005)

8. Eppstein, D.: Dynamic Euclidean Minimum Spanning Trees and Extrema of Binary Functions. Discret. Comput. Geom. 13,111-122(1995)

9. Gabow, H.N., Bentley, J.L., Tarjan, R.E.: Scaling and Related Techniques for Geometry Problems. In: STOC 1984, pp. 135-143

10. Krznaric, D., Levcopoulos, C., Nilsson, B.J.: Minimum Spanning Trees in d Dimensions. Nord. J. Comput. 6(4), 446^61 (1999)

11. Narasimhan, G., Zachariasen, M.: Geometric Minimum Spanning Trees via Well-Separated Pair Decompositions. ACM J. Exp. Algorithms 6,6 (2001)

12. Salowe, J.S.: Constructing multidimensional spanner graphs. Int. J. Comput. Geom. Appl. 1(2), 99-107 (1991)

13. Vaidya, P.M.: Minimum Spanning Trees in k-Dimensional Space. SIAM J. Comput. 17(3), 572-582 (1988)

14. Yao, A.C.: On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems. SIAM J. Comput. 11(4),721-736 (1982)