Применение геометрических остовных сетей: различия между версиями
Irina (обсуждение | вклад) м (→Применение) |
Irina (обсуждение | вклад) м (→Применение) |
||
Строка 97: | Строка 97: | ||
'''Теорема 9. Пусть даны | '''Теорема 9. Пусть даны геометрический граф с n точек и m ребер и константа C, являющаяся верхней границей протяженности t графа G. Тогда за время O(m + nlog n) возможно вычислить <math>(1 + \varepsilon) \; </math>-аппроксимацию t.''' | ||
== Открытые вопросы == | == Открытые вопросы == |
Версия от 12:55, 28 октября 2016
Ключевые слова и синонимы
Постановка задачи
Пусть дан геометрический граф в d-мерном пространстве. Было бы полезно предварительно обработать его таким образом, чтобы можно было эффективно отвечать на запросы о расстояниях (точно или приближенно). Алгоритмы, которые могут отвечать на запросы о расстояниях за константное время, называются также оракулами расстояния. Очевидно, что при неограниченном времени и памяти для предварительной обработки можно легко построить точные оракулы расстояния. Далее будет рассмотрена разработка приближенных оракулов расстояния при ограниченных значениях времени и памяти для предварительной обработки для семейства геометрических графов с константной протяженностью.
Нотация и определения
Пусть p и q – точки в пространстве
Все рассматриваемые далее сети будут считаться простыми и неориентированными. В качестве модели вычислений используется традиционная алгебраическая модель дерева вычислений, дополненная возможностями косвенной адресации. В частности, представленные далее алгоритмы не используют неалгебраическую функцию типа «пол» (округление до целого числа в меньшую сторону) в качестве операции с единичным временем. Формальное определение задачи выглядит следующим образом.
Задача 1 (оракул расстояния). Пусть даны произвольная вещественная константа
Эта структура данных также может быть применена к некоторым другим задачам, среди которых можно упомянуть (1) задачу нахождения приближенного ответа на запросы о расстоянии между вершинами в планарной многоугольной области с «ограниченными» препятствиями, (2) варианты запросов о нахождении пар ближайших точек и (3) эффективное вычисление приближенной протяженности геометрических графов.
Обзор родственных исследований
Над разработкой эффективных структур данных для ответа на запросы о расстоянии для сетей общего вида (не геометрических) работали Торуп и Цвик [15] (они рассматривали невзвешенные графы общего вида), Басванна и Сен [3] (взвешенные графы общего вида, то есть произвольные метрики), а также Арикати и др. [2] и Торуп [14] (взвешенные планарные графы).
Различные варианты задачи для геометрического случая рассматривались во множестве работ; см., например, Чен и др. [5]. Приближенные версии этих вариантов также можно найти во множестве публикаций, в числе которых Агарвал и др. [1]. В основу данной статьи легли результаты, приведенные в работах Гудмундссона и др. [9, 10, 11, 12].
Основные результаты
Основным результатом исследований можно считать существование структур данных для приближенного вычисления оракула расстояния в геометрических сетях с константной протяженностью (см. теорему 4). В качестве предварительной обработки производится «усечение» сети таким образом, чтобы у нее осталось только линейное количество ребер. Структура данных состоит из серий «кластерных графов» возрастающей крупности, каждый из которых позволяет отвечать на приближенные запросы о взаимных расстояниях для пар точек в разных масштабах. Для точного указания подходящего кластерного графа, отвечающего на заданный запрос, структура данных использует инструмент группировки, описанный ниже. Идею использования кластерных графов для ускорения геометрических алгоритмов первыми предложили Дас и Нарасимхан [6], позднее ее же использовали Гудмундссон и др. [8] для разработки эффективного алгоритма вычисления
Усечение
Если количество ребер входной геометрической сети является сверхлинейным, то этап предварительной обработки структуры данных оракула расстояния эффективно «усекает» сеть таким образом, чтобы количество ребер стало линейным. В результате усечения протяженность остова может немного увеличиться. Нижеследующую теорему доказали Гудмундссон и др. [12].
Теорема 1. Пусть t > 1 и
Этап усечения требует использования следующей теоремы, также доказанной Гудмундссоном и др. [12].
Теорема 2. Пусть S – множество из n точек в пространстве
1. последовательность
2. последовательность
так, что верно следующее:
для любых двух различных точек p и q в множестве S возможно за время O(1) вычислить индекс i,
Несмотря на техническую природу этой теоремы, она имеет фундаментальное значение для решения нашей задачи. В частности, она помогает работать с сетями, в которых расстояния между вершинами не ограничиваются полиномиальным диапазоном, т.е. есть пары точек, очень близкие друг к другу, а есть – очень далекие друг от друга.
Группировка
Поскольку предполагаемая в данном случае вычислительная модель не допускает использования функций типа «пол», важным компонентом алгоритма является «инструмент группировки», позволяющий, после соответствующей предварительной обработки, за константное время вычислять величину под названием BIndex, обозначающую округление до целого числа в меньшую сторону логарифма расстояния между любой парой входных точек.
Теорема 3. Пусть S – множество из n точек в пространстве
Упомянутое в теореме 3 вычисление за константное время осуществляется посредством сведения задачи к задаче нахождения ответов на запросы о наименьшем общем предке для пар вершин дерева, для которой Бендер и Фарах-Колтон недавно предложили решение с константным временем выполнения [4].
Основные результаты
Используя инструменты группировки и усечения, а также алгоритмы Гудмундссона и др. [11], можно доказать следующую теорему.
Теорема 4. Пусть t > 1 и
Кроме того, если предполагается использование традиционной алгебраической модели вычислений (без косвенной адресации), можно доказать следующий, более слабый результат.
Теорема 5. Пусть S – множество из n точек в пространстве
Применение
Как упоминалось ранее, вышеописанная структура данных может быть применена к некоторым другим задачам. Во-первых, это поиск ответов на запросы о расстоянии для планарной области с препятствиями в виде многоугольников. Более того, область к тому же должна быть t-ограниченной, что означает, что длина кратчайшего пути, огибающего препятствия, между любыми двумя точками входного множества, не более чем в t раз превышает евклидово расстояние между ними. Иными словами, граф видимости должен быть t-остовом входного множества точек.
Теорема 6. Пусть
Вторым вариантом применения структуры данных оракула расстояния являются версии запросов из задач о вычислении пары ближайших точек, где запросы ограничены определенными подмножествами входного множества.
Теорема 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'|)
Теорема 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|))
И, наконец, еще один вариант применения структуры данных оракула расстояния включает эффективное вычисление приближенной протяженности геометрических графов.
Теорема 9. Пусть даны геометрический граф с n точек и m ребер и константа C, являющаяся верхней границей протяженности t графа G. Тогда за время O(m + nlog n) возможно вычислить
Открытые вопросы
Остаются нерешенными две задачи.
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)