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

В евклидовой метрике 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.

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

Также соблюдается следующий инвариант: для любой фазы алгоритма, создающей ребра длины <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>.

Кэллахан и Косарайю [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 при вставке или удалении точек.

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

* ''[[Остовное дерево с максимальным количеством листьев]]