4430
правок
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) м (→См. также) |
||
(не показано 12 промежуточных версий этого же участника) | |||
Строка 15: | Строка 15: | ||
Эта структура данных также может быть применена к некоторым другим задачам, среди которых можно упомянуть (1) задачу нахождения приближенного ответа на запросы о расстоянии между вершинами в планарной многоугольной области с | Эта структура данных также может быть применена к некоторым другим задачам, среди которых можно упомянуть (1) задачу нахождения приближенного ответа на запросы о расстоянии между вершинами в планарной многоугольной области с «ограниченными» препятствиями, (2) варианты запросов о нахождении пар ''ближайших точек'' и (3) эффективное вычисление приближенной протяженности геометрических графов. | ||
'''Обзор родственных исследований''' | |||
Над разработкой эффективных структур данных для ответа на запросы о расстоянии для сетей общего вида (не геометрических) работали Торуп и Цвик [15] (они рассматривали невзвешенные графы общего вида), Басванна и Сен [3] (взвешенные графы общего вида, то есть произвольные метрики), а также Арикати и др. [2] и Торуп [14] (взвешенные планарные графы). | Над разработкой эффективных структур данных для ответа на запросы о расстоянии для сетей общего вида (не геометрических) работали Торуп и Цвик [15] (они рассматривали невзвешенные графы общего вида), Басванна и Сен [3] (взвешенные графы общего вида, то есть произвольные метрики), а также Арикати и др. [2] и Торуп [14] (взвешенные планарные графы). | ||
Различные варианты задачи для геометрического случая рассматривались во множестве работ; см., например, Чен и др. [5] | Различные варианты задачи для геометрического случая рассматривались во множестве работ; см., например, Чен и др. [5]. Приближенные версии этих вариантов также можно найти во множестве публикаций, в числе которых Агарвал и др. [1]. В основу данной статьи легли результаты, приведенные в работах Гудмундссона и др. [9, 10, 11, 12]. | ||
== Основные результаты == | == Основные результаты == | ||
Основным результатом исследований можно считать существование структур данных для приближенного вычисления оракула расстояния в геометрических сетях с константной протяженностью (см. теорему 4). В качестве предварительной обработки производится «усечение» сети таким образом, чтобы у нее осталось только линейное количество ребер. Структура данных состоит из серий «кластерных графов» возрастающей крупности, каждый из которых позволяет отвечать на приближенные запросы о взаимных расстояниях для пар точек в разных масштабах. Для точного | Основным результатом исследований можно считать существование структур данных для приближенного вычисления оракула расстояния в геометрических сетях с константной протяженностью (см. теорему 4). В качестве предварительной обработки производится «усечение» сети таким образом, чтобы у нее осталось только линейное количество ребер. Структура данных состоит из серий «кластерных графов» возрастающей крупности, каждый из которых позволяет отвечать на приближенные запросы о взаимных расстояниях для пар точек в разных масштабах. Для точного указания подходящего кластерного графа, отвечающего на заданный запрос, структура данных использует инструмент группировки, описанный ниже. Идею использования кластерных графов для ускорения геометрических алгоритмов первыми предложили Дас и Нарасимхан [6], позднее ее же использовали Гудмундссон и др. [8] для разработки эффективного алгоритма вычисления <math>(1 + \varepsilon) \;</math>-остовов. Схожие идеи Гао и др. [7] применяли в приложениях для конструирования мобильных сетей. | ||
'''Усечение''' | '''Усечение''' | ||
Если | Если количество ребер входной геометрической сети является сверхлинейным, то этап предварительной обработки структуры данных оракула расстояния эффективно «усекает» сеть таким образом, чтобы количество ребер стало линейным. В результате усечения протяженность остова может немного увеличиться. Нижеследующую теорему доказали Гудмундссон и др. [12]. | ||
Строка 38: | Строка 40: | ||
'''Теорема 2. Пусть S – множество из n точек в пространстве <math>\mathbb{R}^d \;</math>, а <math>c \ge 7 \;</math> – целочисленная константа. За время O(n log n) можно вычислить структуру данных D(S), в которую входят: | '''Теорема 2. Пусть S – множество из n точек в пространстве <math>\mathbb{R}^d \;</math>, а <math>c \ge 7 \;</math> – целочисленная константа. За время O(n log n) можно вычислить структуру данных D(S), в которую входят:''' | ||
1. последовательность <math>L_1, L_2, ..., L_{\ell} \;</math> вещественных чисел, где <math>\ell = O(n) \;</math>, и | '''1. последовательность <math>L_1, L_2, ..., L_{\ell} \;</math> вещественных чисел, где <math>\ell = O(n) \;</math>, и''' | ||
2. последовательность <math>S_1, S_2, ..., S_{\ell} \;</math> подмножеств S, удовлетворяющих соотношению <math>\sum_{i = 1}^{\ell} |S_i| = O(n) \;</math>, | '''2. последовательность <math>S_1, S_2, ..., S_{\ell} \;</math> подмножеств S, удовлетворяющих соотношению <math>\sum_{i = 1}^{\ell} |S_i| = O(n) \;</math>,''' | ||
так, что верно следующее: | '''так, что верно следующее:''' | ||
для любых двух различных точек p и q в множестве S возможно за время O(1) вычислить индекс i, <math>1 \le i \le \ell \;</math>, и две точки x и y в множестве <math>S_i \;</math>, такие, что (1) <math>L_i / n^{c + 1} \le |xy| < L_i \;</math>; (2) и |px|, и |qy| меньше <math>|xy| / n^{c - 2} \;</math>.''' | '''для любых двух различных точек p и q в множестве S возможно за время O(1) вычислить индекс i, <math>1 \le i \le \ell \;</math>, и две точки x и y в множестве <math>S_i \;</math>, такие, что (1) <math>L_i / n^{c + 1} \le |xy| < L_i \;</math>; (2) и |px|, и |qy| меньше <math>|xy| / n^{c - 2} \;</math>.''' | ||
Строка 54: | Строка 56: | ||
'''Группировка''' | '''Группировка''' | ||
Поскольку предполагаемая в данном случае вычислительная модель не допускает использования функций типа «пол», важным компонентом алгоритма является «инструмент группировки», позволяющий, после соответствующей предварительной обработки, за константное время вычислять величину под названием | Поскольку предполагаемая в данном случае вычислительная модель не допускает использования функций типа «пол», важным компонентом алгоритма является «инструмент группировки», позволяющий, после соответствующей предварительной обработки, за константное время вычислять величину под названием BIndex, обозначающую округление до целого числа в меньшую сторону логарифма расстояния между любой парой входных точек. | ||
Строка 62: | Строка 64: | ||
Упомянутое в теореме 3 вычисление за константное время осуществляется посредством сведения задачи к задаче нахождения ответов на запросы о наименьшем общем предке для пар вершин дерева, для которой Бендер и Фарах-Колтон недавно предложили решение с константным временем выполнения [4]. | Упомянутое в теореме 3 вычисление за константное время осуществляется посредством сведения задачи к задаче нахождения ответов на запросы о наименьшем общем предке для пар вершин дерева, для которой Бендер и Фарах-Колтон недавно предложили решение с константным временем выполнения [4]. | ||
'''Основные результаты''' | |||
Используя инструменты группировки и усечения, а также алгоритмы Гудмундссона и др. [11], можно доказать следующую теорему. | Используя инструменты группировки и усечения, а также алгоритмы Гудмундссона и др. [11], можно доказать следующую теорему. | ||
'''Теорема 4. Пусть t > 1 и <math>\varepsilon > 0 \;</math> – вещественные константы. Пусть S – множество из n точек в пространстве <math>\mathbb{R}^d \;</math>, а G = (S, E) – t-остов для S, имеющий m ребер. Граф G за время O(m + nlog n) может быть преобразован в структуру данных размера O(n log n), такую, что для любых двух точек p и q в S возможно вычислить за время O(1) <math>(1 + \varepsilon) \; </math>-аппроксимацию расстояния по кратчайшему пути в G между p и q. | '''Теорема 4. Пусть t > 1 и <math>\varepsilon > 0 \;</math> – вещественные константы. Пусть S – множество из n точек в пространстве <math>\mathbb{R}^d \;</math>, а G = (S, E) – t-остов для S, имеющий m ребер. Граф G за время O(m + nlog n) может быть преобразован в структуру данных размера O(n log n), такую, что для любых двух точек p и q в S возможно вычислить за время O(1) <math>(1 + \varepsilon) \; </math>-аппроксимацию расстояния по кратчайшему пути в G между p и q. Отметим, что все O-нотации скрывают константы, зависящие от d, t и <math>\varepsilon \;</math>.''' | ||
Строка 87: | Строка 91: | ||
'''Теорема 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|)) <math>(1 + \varepsilon) \; </math>-аппроксимацию бихроматической пары ближайших точек (расстояния измеряются по G).''' | '''Теорема 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|)) <math>(1 + \varepsilon) \; </math>-аппроксимацию бихроматической пары ближайших точек (расстояния измеряются по G).''' | ||
Строка 93: | Строка 97: | ||
'''Теорема 9. Пусть даны | '''Теорема 9. Пусть даны геометрический граф с n точек и m ребер и константа C, являющаяся верхней границей протяженности t графа G. Тогда за время O(m + nlog n) возможно вычислить <math>(1 + \varepsilon) \; </math>-аппроксимацию t.''' | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Строка 103: | Строка 107: | ||
== См. также == | == См. также == | ||
* | * [[Алгоритм поиска кратчайших путей между всеми парами в разреженных графах]] | ||
* | * [[Алгоритм поиска кратчайших путей между всеми парами при помощи матричного произведения]] | ||
* | * [[Геометрические остовы]] | ||
* | * [[Планарные геометрические остовы]] | ||
* | * [[Разреженные остовы графов]] | ||
* | * [[Синхронизаторы и остовы]] | ||
== Литература == | == Литература == |
правок