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

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

'''Определение 1'''. Пусть S – множество точек в пространстве <math>\mathcal{R}^d \;</math>, а s > 0 – вещественное число. ''Декомпозицией значительно удаленных пар'' (well-separated pair decomposition, WSPD) для S относительно s является последовательность <math>\{ A_i, B_i \} , 1 \le i \le m \;</math>, пар непустых подмножеств S, таких, что (1) Ai \ B i = ; для всех i = 1, 2, ... , m; (2) для каждой неориентированной пары {p, q} различных точек S существует ровно одна пара {Ai, Bi} в последовательности, такая, что p 2 Ai и q 2 Bi либо p 2 Bi и q 2 Ai; (3) Ai и Bi являются значительно удаленными относительно s для всех i = 1, 2, ... , m.