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

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

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

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

Пусть дан геометрический граф в 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.

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

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

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

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

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

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

Теорема 4. Пусть t > 1 и " > 0 – вещественные константы. Пусть S – множество из n точек в пространстве Rd, а G = (S, E) – t-остов для S, имеющий m ребер. Граф G за время O(m + nlog n) может быть преобразован в структуру данных размера O(n log n), такую, что для любых двух точек p и q в S возможно вычислить за время O(1) (1 + ")-аппроксимацию расстояния по кратчайшему пути в G между p и q. Отметит, что все O-нотации скрывают константы, зависящие от d, t и ".

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

Теорема 5. Пусть S – множество из n точек в пространстве Rd, а 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) (1 + ")-аппроксимацию расстояния по кратчайшему пути в G между p и q.