4551
правка
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
Строка 32: | Строка 32: | ||
'''<math>\Theta \;</math>-граф''' | '''<math>\Theta \;</math>-граф''' | ||
<math>\Theta \;</math>-графы были независимо разработаны в конце 80-х Кларксоном и Кейлом. Основная идея заключалась в независимой обработке каждой точки p | <math>\Theta \;</math>-графы были независимо разработаны в конце 80-х Кларксоном и Кейлом. Основная идея заключалась в независимой обработке каждой точки <math>p \in S \;</math> следующим образом. Разобьем пространство <math>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. | ||
правка