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

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