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

Остовы на точках в евклидовом пространстве

Максимально изученными классами t-остовных сетей для точек в евклидовом пространстве являются ©-графы, WSPD-графы и жадные остовы. В следующих разделах будут изложены базовые идеи, лежащие в основе каждого из этих классов, а также приведены известные границы мер качества.

©-граф

©-графы были независимо разработаны в конце 80-х Кларксоном и Кейлом. Основная идея заключалась в независимой обработке каждой точки p 2 S следующим образом. Разобьем Rd на k симплициальных конусов с угловым диаметром не более 9 и вершиной в точке p, где k = O(l/9d~1). К каждому непустому конусу C добавляется ребро, связывающее p и точку в C, ортогональная проекция которой на некоторый фиксированный луч в C, исходящий из p, является максимально близкой к p (см. рис. 1a). Полученный граф называется ©-графом на S.

Теорема 1. ©-граф представляет собой t-остов на множестве S для t = 1/ (cos 9 — sin 9), имеющий O{nl9d~l) ребер, и может быть вычислен за время O((n/9d-1)logd~1 n) с использованием O(n/9d-1 + nlogd~2 n) памяти.

Следующие варианты ©-графов задают границы на степень, диаметр и вес.

a: ©-граф. b: граф с нерабочей областью

Задача заключается в обобщении понятия списков с пропусками и применения их к построению остовов. Построим последовательность из h подмножеств, S1, S2, ... Sh, где S1 = S, а Si строится из Si-1 следующим образом (напоминающим уровни в списке пропусков). Для каждой точки в S-1 подбросим симметричную монету. Множество Si включает все точки S-1, для которых монета упала лицевой стороной вверх. Процесс построения заканчивается, когда Si = ;. Для каждого подмножества строится ©-граф. Объединение графов представляет собой остов S на базе списков с пропусками, имеющий протяженность t, O(n/9d~1) ребер и диаметр O(log n) с высокой вероятностью [3].

Одна и та же точка v может быть частью нескольких значительно удаленных пар, и каждая из этих пар может сгенерировать ребро с конечной точкой в v. Арья и др. [ ] предложили алгоритм, сохраняющий только самое короткое ребро для каждого направления конуса, объединив таким образом подход к построению ©-графа с подходом для WSPD-графа. Добавив шаг постобработки, рассматривающий все вершины с высокой степенью, можно получить t-остов степени O(ll{t-l)2d-1).

Дас [9] показал, что t-остов графа видимости для множества точек на евклидовой плоскости можно построить при помощи алгоритма построения ©-графа с последующим этапом усечения. Полученный граф будет иметь линейный размер и константную степень.