4551
правка
Геометрические остовы: различия между версиями
Перейти к навигации
Перейти к поиску
м
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 35: | Строка 35: | ||
Теорема 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> памяти. | [[Файл:GS_1.png]] | ||
Рисунок 1. a: <math>\Theta \;</math>-граф. b: граф с нерабочей областью | |||
'''Теорема 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> памяти.''' | |||
Следующие варианты <math>\Theta \;</math>-графов задают границы на степень, диаметр и вес. | Следующие варианты <math>\Theta \;</math>-графов задают границы на степень, диаметр и вес. | ||
Остовы на базе списков с пропусками | '''Остовы на базе списков с пропусками''' | ||
Задача заключается в обобщении понятия списков с пропусками и применения их к построению остовов. Построим последовательность из h подмножеств, | Задача заключается в обобщении понятия списков с пропусками и применения их к построению остовов. Построим последовательность из h подмножеств, <math>S_1, ... S_h \;</math>, где <math>S_1 = S \;</math>, а <math>S_i \;</math> строится из <math>S_{i - 1} \;</math> следующим образом (напоминающим уровни в списке пропусков). Для каждой точки в <math>S_{i - 1} \;</math> подбросим симметричную монету. Множество <math>S_i \;</math> включает все точки <math>S_{i - 1} \;</math>, для которых монета упала лицевой стороной вверх. Процесс построения заканчивается, когда <math>S_i = \empty \;</math>. Для каждого подмножества строится <math>\Theta \;</math>-граф. Объединение графов представляет собой остов S на базе списков с пропусками, имеющий протяженность t, <math>O(n / \theta^{d - 1}) \;</math> ребер и диаметр O(log n) с высокой вероятностью [3]. | ||
Жадный подход с пробелами | '''Жадный подход с пробелами''' | ||
Множество ориентированных ребер удовлетворяет свойству пробелов, если источники любых двух разных ребер разделены расстоянием, по крайней мере в несколько раз превышающим длины кратчайшего из двух ребер. Арья и Смид [5] предложили алгоритм, использующий свойство пробелов для определения того, может ли некоторое ребро быть добавлено к t-остовному графу. Используя свойство пробелов, можно доказать, что построенный остов имеет степень O{ll9d~l) и вес O(log n • wt(MST(S))), где wt(MST(S)) – вес минимального остовного дерева S. | Множество ориентированных ребер удовлетворяет свойству пробелов, если источники любых двух разных ребер разделены расстоянием, по крайней мере в несколько раз превышающим длины кратчайшего из двух ребер. Арья и Смид [5] предложили алгоритм, использующий свойство пробелов для определения того, может ли некоторое ребро быть добавлено к t-остовному графу. Используя свойство пробелов, можно доказать, что построенный остов имеет степень O{ll9d~l) и вес O(log n • wt(MST(S))), где wt(MST(S)) – вес минимального остовного дерева S. | ||