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

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