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

Кэллахан и Косарайю [ ] показали, что остовное дерево, длина которого отличается от длины MST не более чем на множитель 1 + e, может быть вычислено за время O (n (log n + e ~d/2 log e ~ 1)). Алгоритмы аппроксимации с менее оптимальным соотношением времени и качества ранее предложили Кларксон [6], Вайдья [13] и Салоу [12]. Кроме того, если исходный набор точек поддерживается определенными базовыми структурами данных, то приблизительная длина MST может быть вычислена за рандомизированное сублинейное время [ ]. Эпштейн [ ] предложил полностью динамические алгоритмы, сохраняющие MST при вставке или удалении точек.