4430
правок
Применение геометрических остовных сетей: различия между версиями
Перейти к навигации
Перейти к поиску
Применение геометрических остовных сетей (посмотреть исходный код)
Версия от 00:03, 28 октября 2016
, 28 октября 2016→Нотация и определения
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 6: | Строка 6: | ||
== Нотация и определения == | == Нотация и определения == | ||
Пусть p и q – точки в пространстве <math>\mathbb{R}^d \;</math>. Будем использовать нотацию |pq| для обозначения евклидова расстояния между p и q, а нотацию <math>\delta_G (p q) \;</math> – для обозначения евклидовой длины кратчайшего пути между p и q в геометрической сети G. Пусть имеется константа t > 1. Граф G с множеством вершин S является t-остовом для S, если <math>\delta_G (p q) \le |p q| \;</math> для любых двух точек p и q из S. t-остовная сеть имеет [[протяженность]] (или растяжение) t. <math>(1 + \ | Пусть p и q – точки в пространстве <math>\mathbb{R}^d \;</math>. Будем использовать нотацию |pq| для обозначения евклидова расстояния между p и q, а нотацию <math>\delta_G (p q) \;</math> – для обозначения евклидовой длины кратчайшего пути между p и q в геометрической сети G. Пусть имеется константа t > 1. Граф G с множеством вершин S является t-остовом для S, если <math>\delta_G (p q) \le |p q| \;</math> для любых двух точек p и q из S. t-остовная сеть имеет [[протяженность]] (или растяжение) t. <math>(1 + \varepsilon)</math>-аппроксимацией кратчайшего пути между p и q является любой путь в графе G между p и q, имеющий длину <math>\Delta \;</math>, где <math>\delta_G (p q) \le \Delta \le (1 + \varepsilon)\delta_G (p q) \;</math> . Исчерпывающий обзор геометрических остовов можно найти в работе Нарасимхана и Смида [13]. | ||
Все рассматриваемые далее сети будут считаться простыми и неориентированными. В качестве модели вычислений используется традиционная алгебраическая модель дерева вычислений, дополненная возможностями косвенной адресации. В частности, представленные далее алгоритмы не используют неалгебраическую функцию типа «пол» (округление до целого числа в меньшую сторону) в качестве операции с единичным временем. Формальное определение задачи выглядит следующим образом. | Все рассматриваемые далее сети будут считаться простыми и неориентированными. В качестве модели вычислений используется традиционная алгебраическая модель дерева вычислений, дополненная возможностями косвенной адресации. В частности, представленные далее алгоритмы не используют неалгебраическую функцию типа «пол» (округление до целого числа в меньшую сторону) в качестве операции с единичным временем. Формальное определение задачи выглядит следующим образом. | ||
''' | |||
Задача 1 (оракул расстояния)'''. Пусть даны произвольная вещественная константа <math>\varepsilon > 0 \;</math> и геометрический граф G в d-мерном евклидовом пространстве с константной протяженностью t. Необходимо построить структуру данных, отвечающую на запросы об <math>(1 + \varepsilon)</math>-аппроксимации кратчайшего пути за константное время. | |||
Эта структура данных также может быть применена к некоторым другим задачам, среди которых можно упомянуть (1) задачу нахождения приближенного ответа на запросы о расстоянии между вершинами в планарной многоугольной области с «скругленными» препятствиями, (2) варианты запросов о нахождении пар ''ближайших точек'' и (3) эффективной вычисление приближенной протяженности геометрических графов. | |||
Эта структура данных также может быть применена к некоторым другим задачам, среди которых можно упомянуть (1) задачу нахождения приближенного ответа на запросы о расстоянии между вершинами в планарной многоугольной области с «скругленными» препятствиями, (2) варианты запросов о нахождении пар ближайших точек и (3) эффективной вычисление приближенной протяженности геометрических графов. | |||
== Обзор родственных исследований == | == Обзор родственных исследований == | ||