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

'''размер''': количество ребер в графе.

'''степень''': максимальное количество ребер, инцидентных вершине.

'''вес''': сумма весов ребер.

'''диаметр остова''': наименьшее целое число k, такое, что для любой пары вершин u и v из S существует путь в графе между u и v, длиной не более t • |uv| и содержащий не более k ребер.

Далее будут изложены три самых распространенных подхода к построению t-остова на множестве точек в евклидовом пространстве, а также приведено описание процесса построения отказоустойчивых остовов и остовов между многоугольными препятствиями; и, наконец, будут вкратце описаны динамические и кинетические остовы.

<math>\Theta \;</math>-графы были независимо разработаны в конце 80-х Кларксоном и Кейлом. Основная идея заключалась в независимой обработке каждой точки <math>p \in S \;</math> следующим образом. Разобьем пространство <math>\mathcal{R}^d \;</math> на k симплициальных конусов с угловым диаметром не более <math>\theta \;</math> и вершиной в точке p, где <math>k = O(l / \theta^{d - 1}) \;</math>. К каждому непустому конусу C добавляется ребро, связывающее p и точку в C, ортогональная проекция которой на некоторый фиксированный луч в C, исходящий из p, является максимально близкой к p (см. рис. 1a). Полученный граф называется <math>\Theta \;</math>-графом на S.