Применение геометрических остовных сетей: различия между версиями

Эта структура данных также может быть применена к некоторым другим задачам, среди которых можно упомянуть (1) задачу нахождения приближенного ответа на запросы о расстоянии между вершинами в планарной многоугольной области с «скругленными» препятствиями, (2) варианты запросов о нахождении пар ''ближайших точек'' и (3) эффективное вычисление приближенной протяженности геометрических графов.

Если у входной геометрической сети сверхлинейное количество ребер, то этап предварительной обработки структуры данных оракула расстояния эффективно «усекает» сеть таким образом, чтобы количество ребер стало линейным. В результате усечения протяженность остова может немного увеличиться. Нижеследующую теорему доказали Гудмундссон и др. [12].

'''Теорема 2. Пусть S – множество из n точек в пространстве <math>\mathbb{R}^d \;</math>, а <math>c \ge 7 \;</math> – целочисленная константа. За время O(n log n) можно вычислить структуру данных D(S), в которую входят:

1. последовательность <math>L_1, L_2, ..., L_{\ell} \;</math> вещественных чисел, где <math>\ell = O(n) \;</math>, и

2. последовательность <math>S_1, S_2, ..., S_{\ell} \;</math> подмножеств S, удовлетворяющих соотношению <math>\sum_{i = 1}^{\ell} |S_i| = O(n) \;</math>,

так, что верно следующее:

для любых двух различных точек p и q в множестве S возможно за время O(1) вычислить индекс i, <math>1 \le i \le \ell \;</math>, и две точки x и y в множестве <math>S_i \;</math>, такие, что (1) <math>L_i / n^{c + 1} \le |xy| < L_i \;</math>; (2) и |px|, и |qy| меньше <math>|xy| / n^{c - 2} \;</math>.'''

Поскольку предполагаемая в данном случае вычислительная модель не допускает использования функций типа «пол», важным компонентом алгоритма является «инструмент группировки», позволяющий, после соответствующей предварительной обработки, за константное время вычислять величину под названием BINDEX, обозначающую округление до целого числа в меньшую сторону логарифма расстояния между любой парой входных точек.

== Основные результаты ==

'''Теорема 4. Пусть t > 1 и <math>\varepsilon > 0 \;</math> – вещественные константы. Пусть S – множество из n точек в пространстве <math>\mathbb{R}^d \;</math>, а G = (S, E) – t-остов для S, имеющий m ребер. Граф G за время O(m + nlog n) может быть преобразован в структуру данных размера O(n log n), такую, что для любых двух точек p и q в S возможно вычислить за время O(1) <math>(1 + \varepsilon) \; </math>-аппроксимацию расстояния по кратчайшему пути в G между p и q. Отметит, что все O-нотации скрывают константы, зависящие от d, t и <math>\varepsilon \;</math>.'''

'''Теорема 8. Пусть G = (S, E) – геометрический граф с n точек и m ребер, такой, что он является t-остовом S для некоторой константы t > 1. Граф G за время O(m + nlog n) может быть преобразован в структуру данных размера O(n log n), такую, что для двух непересекающихся подмножеств запроса X и Y множества S возможно вычислить за время O((|X| + |Y|)log(|X| + |Y|)) <math>(1 + \varepsilon) \; </math>-аппроксимацию бихроматической пары ближайших точек (расстояния измеряются по G).'''

'''Теорема 9. Пусть даны – геометрический граф с n точек и m ребер и константа C, являющаяся верхней границей протяженности t графа G. Тогда за время O(m + nlog n) возможно вычислить <math>(1 + \varepsilon) \; </math>-аппроксимацию t.'''

*' [[Алгоритм поиска кратчайших путей в разреженных графах]]

*' [[Алгоритм поиска кратчайших путей при помощи матричного произведения]]

*' [[Геометрические остовы]]

*' [[Планарные геометрические остовы]]

*' [[Разреженные остовы графов]]

*' [[Синхронизаторы, остовы]]