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