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

Пусть дан геометрический граф в d-мерном пространстве. Было бы полезно предварительно обработать его таким образом, чтобы можно было эффективно отвечать на запросы о расстояниях (точно или приближенно). Алгоритмы, которые могут отвечать на запросы о расстояниях за константное время, называются также ''оракулами расстояния''. Очевидно, что при неограниченном времени и памяти для предварительной обработки легко можно построить точные оракулы расстояния. Далее будет рассмотрена разработка приближенных оракулов расстояния при ограниченных значениях времени и памяти для предварительной обработки для семейства геометрических графов с константной протяженностью.

Пусть p и q – точки в пространстве <math>\mathbb{R}^d \;</math>. Будем использовать нотацию |pq| для обозначения евклидова расстояния между p и q, а нотацию <math>\delta_G (p q) \;</math> – для обозначения евклидовой длины кратчайшего пути между p и q в геометрической сети G. Пусть имеется константа t > 1. Граф G с множеством вершин S является t-остовом для S, если <math>\delta_G (p q) \le |p q| \;</math>  для любых двух точек p и q из S. t-остовная сеть имеет [[протяженность]] (или растяжение) t. <math>(1 + \varepsilon) \;</math>-аппроксимацией кратчайшего пути между p и q является любой путь в графе G между p и q, имеющий длину <math>\Delta \;</math>, где <math>\delta_G (p q) \le \Delta \le (1 + \varepsilon)\delta_G (p q) \;</math> . Исчерпывающий обзор геометрических остовов можно найти в работе Нарасимхана и Смида [13].

'''Задача 1 (оракул расстояния)'''. Пусть даны произвольная вещественная константа <math>\varepsilon > 0 \;</math> и геометрический граф G в d-мерном евклидовом пространстве с константной протяженностью t. Необходимо построить структуру данных, отвечающую на запросы об <math>(1 + \varepsilon) \; </math>-аппроксимации кратчайшего пути за константное время.

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

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

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

Теорема 3. Пусть S – множество из n точек в пространстве <math>\mathbb{R}^d \;</math>, содержащихся в гиперкубе (0; nk)d для некоторой положительной целочисленной константы k, а " – положительная вещественная константа. Множество S за время O(n log n) может быть преобразовано в структуру данных размера O(n), такую, что для любых двух точек p и q в S, |pq| > 1, возможно вычислить за константное время величину BIndex "(p, q) = blog1+" |pq|c.

Теорема 4. Пусть t > 1 и " > 0 – вещественные константы. Пусть 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 и ".

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

Теорема 6. Пусть F – t-ограниченный набор многоугольных препятствий на плоскости с общей сложностью n, где t – положительная константа. Можно предварительно обработать набор F за время O(n log n), преобразовав его в структуру данных размера O(n log n), способную отвечать на запросы о длине <math>(1 + \varepsilon) \; </math>-аппроксимации кратчайшего пути, минующего препятствия, за время O(log n). Если точками запроса являются вершины F, ответы на запросы можно получить за время O(1).

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

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

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