Применение геометрических остовных сетей

Ключевые слова и синонимы

Коэффициент растяжения

Постановка задачи

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

Нотация и определения

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

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

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

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

Обзор родственных исследований

Над разработкой эффективных структур данных для ответа на запросы о расстоянии для сетей общего вида (не геометрических) работали Торуп и Цвик [15] (они рассматривали невзвешенные графы общего вида), Басванна и Сен [3] (взвешенные графы общего вида, то есть произвольные метрики), а также Арикати и др. [2] и Торуп [14] (взвешенные планарные графы).

Различные варианты задачи для геометрического случая рассматривались во множестве работ; см., например, Чен и др. [5]. Приближенные версии этих вариантов также можно найти во множестве публикаций, в числе которых Агарвал и др. [1]. В основу данной статьи легли результаты, приведенные в работах Гудмундссона и др. [9, 10, 11, 12].

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

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

Усечение

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

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

Этап усечения требует использования следующей теоремы, также доказанной Гудмундссоном и др. [12].

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

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

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

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

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

Несмотря на техническую природу этой теоремы, она имеет фундаментальное значение для решения нашей задачи. В частности, она помогает работать с сетями, в которых расстояния между вершинами не ограничиваются полиномиальным диапазоном, т.е. есть пары точек, очень близкие друг к другу, а есть – очень далекие друг от друга.

Группировка

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

Теорема 3. Пусть S – множество из n точек в пространстве [math]\displaystyle{ \mathbb{R}^d \; }[/math], содержащихся в гиперкубе [math]\displaystyle{ (0, n^k)^d \; }[/math] для некоторой положительной целочисленной константы k, а [math]\displaystyle{ \varepsilon \; }[/math] – положительная вещественная константа. Множество S за время O(n log n) может быть преобразовано в структуру данных размера O(n), такую, что для любых двух точек p и q в S, [math]\displaystyle{ |pq| \ge 1 \; }[/math], возможно вычислить за константное время величину [math]\displaystyle{ BIndex_{ \varepsilon} (p, q) = \lfloor log_{1 + \varepsilon} \; |pq| \rfloor }[/math].

Упомянутое в теореме 3 вычисление за константное время осуществляется посредством сведения задачи к задаче нахождения ответов на запросы о наименьшем общем предке для пар вершин дерева, для которой Бендер и Фарах-Колтон недавно предложили решение с константным временем выполнения [4].

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

Используя инструменты группировки и усечения, а также алгоритмы Гудмундссона и др. [11], можно доказать следующую теорему.

Теорема 4. Пусть t > 1 и [math]\displaystyle{ \varepsilon \gt 0 \; }[/math] – вещественные константы. Пусть S – множество из n точек в пространстве [math]\displaystyle{ \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]\displaystyle{ (1 + \varepsilon) \; }[/math]-аппроксимацию расстояния по кратчайшему пути в G между p и q. Отметим, что все O-нотации скрывают константы, зависящие от d, t и [math]\displaystyle{ \varepsilon \; }[/math].

Кроме того, если предполагается использование традиционной алгебраической модели вычислений (без косвенной адресации), можно доказать следующий, более слабый результат.

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

Применение

Как упоминалось ранее, вышеописанная структура данных может быть применена к некоторым другим задачам. Во-первых, это поиск ответов на запросы о расстоянии для планарной области с препятствиями в виде многоугольников. Более того, область к тому же должна быть t-ограниченной, что означает, что длина кратчайшего пути, огибающего препятствия, между любыми двумя точками входного множества, не более чем в t раз превышает евклидово расстояние между ними. Иными словами, граф видимости должен быть t-остовом входного множества точек.

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

Вторым вариантом применения структуры данных оракула расстояния являются версии запросов из задач о вычислении пары ближайших точек, где запросы ограничены определенными подмножествами входного множества.

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

Теорема 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]\displaystyle{ (1 + \varepsilon) \; }[/math]-аппроксимацию бихроматической пары ближайших точек (расстояния измеряются по G).

И, наконец, еще один вариант применения структуры данных оракула расстояния включает эффективное вычисление приближенной протяженности геометрических графов.

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

Открытые вопросы

Остаются нерешенными две задачи.

1. Улучшение объема используемой структурой данных оракула расстояния памяти – с O(n log n) до O(n).

2. Расширение структуры данных оракула расстояния, позволяющее выдавать не только приблизительное расстояние, но и приблизительный кратчайший путь между заданными в запросе точками.

См. также

• Алгоритм поиска кратчайших путей между всеми парами в разреженных графах
• Алгоритм поиска кратчайших путей между всеми парами при помощи матричного произведения
• Геометрические остовы
• Планарные геометрические остовы
• Разреженные остовы графов
• Синхронизаторы и остовы

Литература

1. Agarwal, P.K., Har-Peled, S., Karia, M.: Computing approximate shortest paths on convex polytopes. In: Proceedings of the 16th ACM Symposium on Computational Geometry, pp. 270-279. ACM Press, New York (2000)

2. Arikati, S., Chen, D.Z., Chew, L.P., Das, G., Smid, M., Zaroliagis, C.D.: Planar spanners and approximate shortest path queries among obstacles in the plane. In: Proceedings of the 4th Annual European Symposium on Algorithms. Lecture Notes in Computer Science, vol. 1136, Berlin, pp. 514-528. Springer, London (1996)

3. Baswana, S., Sen, S.: Approximate distance oracles for unweighted graphs in 6(n2) time. In: Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms, pp. 271-280. ACM Press, New York (2004)

4. Bender, M.A., Farach-Colton, M.: The LCA problem revisited. In: Proceedings of the4th Latin American Symposium on Theoretical Informatics. Lecture Notes in Computer Science, vol. 1776, Berlin, pp. 88-94. Springer, London (2000)

5. Chen, D.Z., Daescu, O., Klenk, K.S.: On geometric path query problems. Int. J. Comput. Geom. Appl. 11,617-645 (2001)

6. Das, G., Narasimhan, G.: A fast algorithm for constructing sparse Euclidean spanners. Int. J. Comput. Geom. Appl. 7,297-315(1997)

7. Gao, J., Guibas, L.J., Hershberger, J., Zhang, L., Zhu, A.: Discrete mobile centers. Discrete Comput. Geom. 30,45-63 (2003)

8. Gudmundsson, J., Levcopoulos, C., Narasimhan, G.: Fast greedy algorithms for constructing sparse geometric spanners. SIAM J. Comput. 31,1479-1500 (2002)

9. Gudmundsson, J., Levcopoulos, C., Narasimhan, G., Smid, M.: Approximate distance oracles for geometric graphs. In: Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms, pp. 828-837. ACM Press, New York (2002)

10. Gudmundsson, J., Levcopoulos, C., Narasimhan, G., Smid, M.: Approximate distance oracles revisited. In: Proceedings of the 13th International Symposium on Algorithms and Computation. Lecture Notes in Computer Science, vol. 2518, Berlin, pp. 357-368. Springer, London (2002)

11. Gudmundsson, J., Levcopoulos, C., Narasimhan, G., Smid, M.: Approximate distance oracles for geometric spanners, ACM Trans. Algorithms (2008). To Appear

12. Gudmundsson, J., Narasimhan, G., Smid, M.: Fast pruning of geometric spanners. In: Proceedings of the 22nd Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science, vol. 3404, Berlin, pp. 508-520. Springer, London (2005)

13. Narasimhan, G., Smid, M.: Geometric Spanner Networks, Cambridge University Press, Cambridge, UK (2007)

14. Thorup, M.: Compact oracles for reachability and approximate distances in planar digraphs. J. ACM 51,993-1024 (2004)

15. Thorup, M., Zwick, U.: Approximate distance oracles. In: Proceedings of the 33rd Annual ACM Symposium on the Theory of Computing, pp. 183-192. ACM Press, New York (2001)