4551
правка
Применение геометрических остовных сетей: различия между версиями
Перейти к навигации
Перейти к поиску
Применение геометрических остовных сетей (посмотреть исходный код)
Версия от 17:18, 13 октября 2016
, 13 октября 2016→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 28: | Строка 28: | ||
'''Усечение''' | '''Усечение''' | ||
Если у входной геометрической сети сверхлинейное количество ребер, то этап предварительной обработки структуры данных оракула расстояния эффективно «усекает» сеть таким образом, чтобы количество ребер стало линейным. В результате усечения протяженность остова может немного увеличиться. Нижеследующую теорему доказали Гудмундссон и др. [12]. | |||
Теорема 1. Пусть t > 1 и "0 > 0 – вещественные константы. Пусть S – множество из n точек в пространстве Rd, а G = (S, E) – t-остов для S, имеющий m ребер. Существует алгоритм, за время O(m + nlog n) вычисляющий (1 + "0)-остов G, имеющий O(n) ребер и вес O(wt(MST(S))). | |||
Этап усечения требует использования следующей теоремы, также доказанной Гудмундссоном и др. [12]. | |||
Теорема 2. Пусть S – множество из n точек в пространстве Rd, а c > 7 – целочисленная константа. За время O(n log n) можно вычислить структуру данных D(S), в которую входят: | |||
1. последовательность L1, L2, ... Li вещественных чисел, где I = O(n), и | |||
2. последовательность S1, S2, ... Si подмножеств S, удовлетворяющих | |||
так, что верно следующее: | |||
для любых двух различных точек p и q в множестве S возможно за время O(1) вычислить индекс i, 1 < i < I, и две точки x и y в множестве Si, такие, что (1) Li/nc+1 < |xy| < Li; (2) и |px|, и |qy| меньше \xy\lnc~2. | |||
Несмотря на техническую природу этой теоремы, она имеет фундаментальное значение для решения нашей задачи. В частности, она помогает работать с сетями, в которых расстояния между вершинами не ограничиваются полиномиальным диапазоном, т.е. есть пары точек, очень близкие друг к другу, а есть – очень далекие друг от друга. | |||
'''Группировка''' | |||