Минимальные геометрические остовные деревья: различия между версиями
Irina (обсуждение | вклад) м (→См. также) |
KVN (обсуждение | вклад) |
||
| (не показано 13 промежуточных версий 1 участника) | |||
| Строка 2: | Строка 2: | ||
Остовные деревья минимальной длины; остовные деревья минимального веса; минимальные евклидовы остовные деревья; MST; EMST | Остовные деревья минимальной длины; остовные деревья минимального веса; минимальные евклидовы остовные деревья; MST; EMST | ||
== Постановка задачи == | == Постановка задачи == | ||
Пусть S – множество из n точек в d-мерном вещественном пространстве, где d – целочисленная константа | Пусть 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>. | ||
== Основные результаты == | == Основные результаты == | ||
| Строка 13: | Строка 11: | ||
В евклидовой метрике L2, где расстояния измеряются по прямой, задача MST в двух измерениях может быть оптимально решена за время O(n log n) с использованием того факта, что MST представляет собой подграф триангуляции Делоне на множестве входных вершин. Последний, в свою очередь, взаимно однозначно соответствует диаграмме Вороного для графа S, для нахождения которой разработано несколько алгоритмов с временем | В евклидовой метрике L2, где расстояния измеряются по прямой, задача MST в двух измерениях может быть оптимально решена за время O(n log n) с использованием того факта, что MST представляет собой подграф триангуляции Делоне на множестве входных вершин. Последний, в свою очередь, взаимно однозначно соответствует диаграмме Вороного для графа S, для нахождения которой разработано несколько алгоритмов с временем выполнения O(n log n). Термин «оптимально» относится к модели алгебраического дерева вычислений. После вычисления триангуляции Делоне вычисление дерева MST можно произвести всего за O(n) дополнительного времени при помощи алгоритма Черитона-Тарьяна [5]. | ||
Даже для более высоких размерностей, т.е. при d > 2, MST представляет собой подграф двойственной диаграммы Вороного; однако этот факт нельзя использовать тем же способом, как в случае двух измерений, поскольку эта двойственная диаграмма может содержать | Даже для более высоких размерностей, т.е. при 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 синих точек (вторая задача носит название задачи нахождения бихроматической пары ближайших точек). Они показали, что если обозначить за | Алгоритм Агарвала и коллег базируется на исследовании отношений между вычислением 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. | ||
| Строка 28: | Строка 26: | ||
Предположим, что следующее ребро, которое собирается создать алгоритм, имеет длину l. Каждое дерево T в лесу подразделяется на группы вершин, каждую из которых представляет одна конкретная вершина. Вершина-представитель такой группы называется ее лидером. Далее, каждая вершина в группе, включая лидера, обладает следующим свойством: она находится от лидера на расстоянии не более | Предположим, что следующее ребро, которое собирается создать алгоритм, имеет длину l. Каждое дерево T в лесу подразделяется на группы вершин, каждую из которых представляет одна конкретная вершина. Вершина-представитель такой группы называется ее ''лидером''. Далее, каждая вершина в группе, включая лидера, обладает следующим свойством: она находится от лидера на расстоянии не более <math>\epsilon \cdot l \;</math>, где <math>\epsilon \;</math> – вещественная константа, близкая к нулю. | ||
Вместо рассмотрения всех пар вершин, которые могли бы быть кандидатами на создание следующего ребра, вначале рассматриваются все пары лидеров. Только в случае, если пара лидеров принадлежит к разным деревьям и расстояние между ними приблизительно равно l, ближайшая пара точек между их соответствующими группами вычисляется при помощи алгоритма нахождения бихроматической пары ближайших точек. | Вместо рассмотрения всех пар вершин, которые могли бы быть кандидатами на создание следующего ребра, вначале рассматриваются все пары лидеров. Только в случае, если пара лидеров принадлежит к разным деревьям и расстояние между ними приблизительно равно 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). | |||
== Приближенные и динамические решения == | == Приближенные и динамические решения == | ||
Кэллахан и Косарайю [ ] показали, что остовное дерево, длина которого отличается от длины MST не более чем на множитель 1 + | Кэллахан и Косарайю [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) входят в число самых базовых структур в таких дисциплинах, как вычислительная геометрия и теория графов, и имеют множество вариантов применения. | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Поскольку сложность вычисления MST связана со сложностью нахождения бихроматических пар ближайших точек, открытые вопросы в этих двух задачах родственны; к ним относятся, например, такие варианты, как работа с числом размерностей выше 3. | Поскольку сложность вычисления MST связана со сложностью нахождения бихроматических пар ближайших точек, открытые вопросы в этих двух задачах родственны; к ним относятся, например, такие варианты, как работа с числом размерностей выше 3. | ||
== Экспериментальные результаты == | == Экспериментальные результаты == | ||
Нарасимхан и Захариасен [ ] провели эксперименты с вычислением минимальных геометрических остовных деревьев при помощи декомпозиции значительно | Нарасимхан и Захариасен [11] провели эксперименты с вычислением минимальных геометрических остовных деревьев при помощи декомпозиции на значительно удаленные пары. | ||
== См. также == | == См. также == | ||
| Строка 72: | Строка 69: | ||
* ''[[Полностью динамические минимальные остовные деревья]] | * ''[[Полностью динамические минимальные остовные деревья]] | ||
* ''[[Жадные алгоритмы покрытия множества]] | * ''[[Жадные алгоритмы покрытия множества]] | ||
* ''[[ | * ''[[Остовное дерево с максимальным количеством листьев]] | ||
* ''[[Минимальные остовные деревья]] | * ''[[Минимальные остовные деревья]] | ||
* ''[[Параллельная связность и минимальные остовные деревья]] | * ''[[Параллельная связность и минимальные остовные деревья]] | ||
| Строка 79: | Строка 76: | ||
* ''[[Прямолинейное дерево Штейнера]] | * ''[[Прямолинейное дерево Штейнера]] | ||
* ''[[Лес Штейнера]] | * ''[[Лес Штейнера]] | ||
* ''[[Деревья Штейнера]] | * ''[[Дерево Штейнера|Деревья Штейнера]] | ||
== Литература == | == Литература == | ||
| Строка 109: | Строка 106: | ||
14. Yao, A.C.: On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems. SIAM J. Comput. 11(4),721-736 (1982) | 14. Yao, A.C.: On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems. SIAM J. Comput. 11(4),721-736 (1982) | ||
[[Категория: Совместное определение связанных терминов]] | |||
Текущая версия от 11:34, 22 ноября 2024
Ключевые слова и синонимы
Остовные деревья минимальной длины; остовные деревья минимального веса; минимальные евклидовы остовные деревья; 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)