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

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

Основным результатом исследований можно считать существование структур данных для приближенного вычисления оракула расстояния в геометрических сетях с константной протяженностью (см. теорему 4). В качестве предварительной обработки производится «усечение» сети таким образом, чтобы у нее осталось только линейное количество ребер. Структура данных состоит из серий «кластерных графов» возрастающей крупности, каждый из которых позволяет отвечать на приближенные запросы о взаимных расстояниях для пар точек в разных масштабах. Для точного нахождения кластерного графа, отвечающего на заданный запрос, структура данных использует инструмент группировки, описанный ниже. Идею использования кластерных графов для ускорения геометрических алгоритмов первыми предложили Дас и Нарасимхан [6], позднее ее же использовали Гудмундссон и др. [8] для разработки эффективного алгоритма вычисления <math>(1 + \varepsilon) \;</math>-остовов. Схожие идеи Гао и др. [7] применяли в приложениях для конструирования мобильных сетей.

Если у входной геометрической сети сверхлинейное количество ребер, то этап предварительной обработки структуры данных оракула расстояния эффективно «усекает» сеть таким образом, чтобы количество ребер стало линейным. В результате усечения протяженность остова может немного увеличиться. Нижеследующую теорему доказали Гудмундссон и др. [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.'''

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

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

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

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

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

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