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