Геометрические остовы: различия между версиями

Для геометрических остовов естественно рассматривать ''отказы областей'' – то есть отказы, уничтожающие все вершины и ребра, пересекающие некоторую нерабочую геометрическую область. Пусть для нерабочей области F граф <math>G \ominus F</math> представляет собой часть G, оставшуюся после того, как точки из S, находящиеся внутри области F, и все ребра, пересекающие F, были удалены из графа; см. рис. 1b. Абам и др. [1] показали, как строить t-остовы размера O(n log n), являющиеся отказоустойчивыми при  отказе любой выпуклой области. Если разрешается использовать [[точка Штейнера|точки Штейнера]], можно получить t-остов линейного размера.

'''Остовы с многоугольными препятствиями'''