4430
правок
Применение геометрических остовных сетей: различия между версиями
Материал из WEGA
Применение геометрических остовных сетей (посмотреть исходный код)
Версия от 11:27, 19 июня 2018
, 19 июня 2018→См. также
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) м (→См. также) |
||
| (не показано 7 промежуточных версий этого же участника) | |||
| Строка 15: | Строка 15: | ||
Эта структура данных также может быть применена к некоторым другим задачам, среди которых можно упомянуть (1) задачу нахождения приближенного ответа на запросы о расстоянии между вершинами в планарной многоугольной области с | Эта структура данных также может быть применена к некоторым другим задачам, среди которых можно упомянуть (1) задачу нахождения приближенного ответа на запросы о расстоянии между вершинами в планарной многоугольной области с «ограниченными» препятствиями, (2) варианты запросов о нахождении пар ''ближайших точек'' и (3) эффективное вычисление приближенной протяженности геометрических графов. | ||
| Строка 56: | Строка 56: | ||
'''Группировка''' | '''Группировка''' | ||
Поскольку предполагаемая в данном случае вычислительная модель не допускает использования функций типа «пол», важным компонентом алгоритма является «инструмент группировки», позволяющий, после соответствующей предварительной обработки, за константное время вычислять величину под названием | Поскольку предполагаемая в данном случае вычислительная модель не допускает использования функций типа «пол», важным компонентом алгоритма является «инструмент группировки», позволяющий, после соответствующей предварительной обработки, за константное время вычислять величину под названием BIndex, обозначающую округление до целого числа в меньшую сторону логарифма расстояния между любой парой входных точек. | ||
| Строка 64: | Строка 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>.''' | ||
| Строка 89: | Строка 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).''' | ||
| Строка 95: | Строка 97: | ||
'''Теорема 9. Пусть даны | '''Теорема 9. Пусть даны геометрический граф с n точек и m ребер и константа C, являющаяся верхней границей протяженности t графа G. Тогда за время O(m + nlog n) возможно вычислить <math>(1 + \varepsilon) \; </math>-аппроксимацию t.''' | ||
== Открытые вопросы == | == Открытые вопросы == | ||
| Строка 105: | Строка 107: | ||
== См. также == | == См. также == | ||
* | * [[Алгоритм поиска кратчайших путей между всеми парами в разреженных графах]] | ||
* | * [[Алгоритм поиска кратчайших путей между всеми парами при помощи матричного произведения]] | ||
* | * [[Геометрические остовы]] | ||
* | * [[Планарные геометрические остовы]] | ||
* | * [[Разреженные остовы графов]] | ||
* | * [[Синхронизаторы и остовы]] | ||
== Литература == | == Литература == | ||
