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

Даже для более высоких размерностей, т.е. при 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> – произвольно малая положительная константа.