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

Если у входной геометрической сети сверхлинейное количество ребер, то этап предварительной обработки структуры данных оракула расстояния эффективно «усекает» сеть таким образом, чтобы количество ребер стало линейным. В результате усечения протяженность остова может немного увеличиться. Нижеследующую теорему доказали Гудмундссон и др. [12].