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

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

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

Также соблюдается следующий инвариант: для любой фазы алгоритма, создающей ребра длины [math]\displaystyle{ \Theta (l) \; }[/math], и для любого лидера существует только константное число других лидеров, находящихся от него на расстоянии [math]\displaystyle{ \Theta (l) \; }[/math]. Таким образом, общее количество подлежащих рассмотрению пар лидеров не более чем линейно относительно количества лидеров.

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

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

К примеру, в метрике [math]\displaystyle{ L_1 \; }[/math] возможно за время O(n log n) построить специальную разновидность планарной диаграммы Вороного для синих точек на плоскости, отделяющей синие точки от красных и имеющей следующее свойство: для каждой рассматриваемой точки q в полупространстве, включающем красные точки, можно использовать эту диаграмму Вороного, чтобы за время O(log n) найти синюю точку, ближайшую к q согласно метрике [math]\displaystyle{ L_1 \; }[/math]. (Можно рассматривать эту планарную диаграмму Вороного как определяемую вертикальными проекциями синих точек на плоскость, содержащую диаграмму, а размер клетки Вороного зависит от расстояния между соответствующей синей точкой и плоскостью). Таким образом, рассматривая последовательно каждую красную точку, можно решить задачу нахождения бихроматической пары ближайших точек для подобных сильно разнесенных красно-синих множеств за полное время O(n log n).

Используя этот подход, Кржнарик и коллеги [10] показали, как вычислить MST для S за оптимальное время O(n log n) согласно метрикам [math]\displaystyle{ L_1 \; }[/math] и [math]\displaystyle{ L_{\infty} \; }[/math] в случае, если d = 3. Время выполнения было улучшено по сравнению с ранее известными границами благодаря работам Габова и коллег [9] и Беспамятных [2], которые доказали, что для d = 3 MST можно вычислить за время O(n log n log log n) согласно метрикам [math]\displaystyle{ L_1 \; }[/math] и [math]\displaystyle{ L_{\infty} \; }[/math].

Основные результаты Кржнарика и коллег [10] можно изложить в следующей теореме.

Теорема. В модели алгебраического дерева вычислений для любой фиксированной [math]\displaystyle{ L_p }[/math]-метрики и любого фиксированного количества размерностей вычисление MST имеет ту же временную сложность в наихудшем случае, с поправкой на константный множитель, что и вычисление бихроматической пары ближайших точек. Кроме того, в трехмерном пространстве с метриками [math]\displaystyle{ L_1 \; }[/math] и [math]\displaystyle{ L_{\infty} \; }[/math] задача MST, также как и вычисление бихроматической пары ближайших точек, требуют оптимального времени вычисления O(n log n).

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

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

Применение

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

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

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

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

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

См. также

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

Литература

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)