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

<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.

'''Теорема 1. <math>\Theta \;</math>-граф представляет собой t-остов на множестве S для <math>t = 1 / (cos \; \theta — sin \; \theta)</math>, имеющий <math>O(n / \theta^{d - 1}) \;</math> ребер, и может быть вычислен за время <math>O((n /  \theta^{d - 1}) log^{d - 1} \; n)</math> с использованием <math>O(n / \theta^{d - 1} + n \; log^{d - 2} \; n)</math> памяти.'''