4551
правка
Применение геометрических остовных сетей: различия между версиями
Перейти к навигации
Перейти к поиску
Применение геометрических остовных сетей (посмотреть исходный код)
Версия от 16:39, 17 октября 2016
, 17 октября 2016→Применение
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 80: | Строка 80: | ||
Вторым вариантом применения структуры данных оракула расстояния являются версии запросов из задач о вычислении пары ближайших точек, где запросы ограничены определенными подмножествами входного множества. | Вторым вариантом применения структуры данных оракула расстояния являются версии запросов из задач о вычислении пары ближайших точек, где запросы ограничены определенными подмножествами входного множества. | ||
Теорема 7. Пусть G = (S, E) – геометрический граф с n точек и m ребер, такой, что он является t-остовом S для некоторой константы t > 1. Граф G за время O(m + nlog n) может быть преобразован в структуру данных размера O(n log n), такую, что для заданного подмножества запроса S0 множества S возможно вычислить за время O(jS0jlogjS0j) (1 + ")-аппроксимацию пары ближайших точек в S0 (расстояния измеряются по G). | |||
Теорема 8. Пусть G = (S, E) – геометрический граф с n точек и m ребер, такой, что он является t-остовом S для некоторой константы t > 1. Граф G за время O(m + nlog n) может быть преобразован в структуру данных размера O(n log n), такую, что для двух непересекающихся подмножеств запроса X и Y множества S возможно вычислить за время O((jXj + jYj)log(jXj + jYj)) (1 + ")-аппроксимацию бихроматической пары ближайших точек (расстояния измеряются по G). | |||
И, наконец, еще один вариант применения структуры данных оракула расстояния включает эффективное вычисление приближенной протяженности геометрических графов. | |||
Теорема 9. Пусть даны – геометрический граф с n точек и m ребер и константа C, являющаяся верхней границей протяженности t графа G. Тогда за время O(m + nlog n) возможно вычислить (1 + ")-аппроксимацию t. | |||
== Открытые вопросы == | |||