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

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

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

Пусть S – множество из n точек в d-мерном вещественном пространстве, где <math>d \ge 1 \;</math> – целочисленная константа. [[Минимальное остовное дерево]] (MST) графа S представляет собой связный ациклический граф с множеством вершин S и минимальной суммарной длиной ребер. Длина ребра равна расстоянию между его конечными точками согласно некоторой метрике. В метрике <math>L_p \;</math> расстояние между двумя точками x и y с координатами <math>(x_1, x_2, ..., x_d) \;</math> и <math>(y_1, y_2, ..., yd_) \;</math>, соответственно, определяется как p-й корень суммы <math>\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>\Omega (n^2) \;</math> ребер. Следовательно, в случае более высоких размерностей для сокращения количества рассматриваемых ребер нужно использовать другие геометрические свойства. Первый алгоритм для высоких размерностей с временем выполнения ниже квадратичного был предложен Яо [14]. Более эффективный алгоритм позднее предложили Агарвал и коллеги [1]. Для случая <math>d = 3 \;</math> их алгоритм выполняется за рандомизированное ожидаемое время <math>O((n \; log n)^{4/3}) \;</math>, а для <math>d \ge 4 \;</math> – за ожидаемое время <math>O(n^{2-2/( \left \lceil d/2 \right \rceil + 1) + \epsilon } ) \;</math>, где <math>\epsilon \;</math> – произвольно малая положительная константа.


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


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


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


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


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


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


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


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


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


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


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


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

== Приближенные и динамические решения ==
Кэллахан и Косарайю [4] показали, что остовное дерево, длина которого отличается от длины MST не более чем на множитель <math>1 + \epsilon \;</math>, может быть вычислено за время <math>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)

[[Категория: Совместное определение связанных терминов]]