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

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

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

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

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

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

Пусть p и q – точки в пространстве Rd. Будем использовать нотацию |pq| для обозначения евклидова расстояния между p и q, а нотацию So(p, q) – для обозначения евклидовой длины кратчайшего пути между p и q в геометрической сети G. Пусть имеется константа t > 1. Граф G с множеством вершин S является t-остовом для S, если Sg(p, q) < t|pq| для любых двух точек p и q из S. t-остовная сеть имеет протяженность (или растяжения) t. (1 + ")-аппроксимацией кратчайшего пути между p и q является любой путь в графе G между p и q, имеющий длину Л, где Sg(p, q) < Л < (1 + Е)8д(р, q). Исчерпывающий обзор геометрических остовов можно найти в работе Нарасимхана и Смида [ ].

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

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

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

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

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

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

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

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

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

Теорема 1. Пусть t > 1 и "0 > 0 – вещественные константы. Пусть S – множество из n точек в пространстве Rd, а G = (S, E) – t-остов для S, имеющий m ребер. Существует алгоритм, за время O(m + nlog n) вычисляющий (1 + "0)-остов G, имеющий O(n) ребер и вес O(wt(MST(S))).

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

Теорема 2. Пусть S – множество из n точек в пространстве Rd, а c > 7 – целочисленная константа. За время O(n log n) можно вычислить структуру данных D(S), в которую входят:

1. последовательность L1, L2, ... Li вещественных чисел, где I = O(n), и

2. последовательность S1, S2, ... Si подмножеств S, удовлетворяющих

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

для любых двух различных точек p и q в множестве S возможно за время O(1) вычислить индекс i, 1 < i < I, и две точки x и y в множестве Si, такие, что (1) Li/nc+1 < |xy| < Li; (2) и |px|, и |qy| меньше \xy\lnc~2.

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

Группировка