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

Материал из WEGA
Перейти к навигации Перейти к поиску
Строка 7: Строка 7:


== Нотация и определения ==
== Нотация и определения ==
Пусть 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) эффективной вычисление приближенной протяженности геометрических графов.
== Обзор родственных исследований ==

Версия от 12:35, 12 октября 2016

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

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

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

Пусть дан геометрический граф в 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) эффективной вычисление приближенной протяженности геометрических графов.

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