4551
правка
Применение геометрических остовных сетей: различия между версиями
Перейти к навигации
Перейти к поиску
Применение геометрических остовных сетей (посмотреть исходный код)
Версия от 00:13, 16 октября 2016
, 16 октября 2016→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 61: | Строка 61: | ||
== Основные результаты == | == Основные результаты == | ||
Используя инструменты группировки и усечения, а также алгоритмы Гудмундссона и др. можно доказать следующую теорему. | |||
Теорема 4. Пусть t > 1 и " > 0 – вещественные константы. Пусть S – множество из n точек в пространстве Rd, а G = (S, E) – t-остов для S, имеющий m ребер. Граф G за время O(m + nlog n) может быть преобразован в структуру данных размера O(n log n), такую, что для любых двух точек p и q в S возможно вычислить за время O(1) (1 + ")-аппроксимацию расстояния по кратчайшему пути в G между p и q. Отметит, что все O-нотации скрывают константы, зависящие от d, t и ". | |||
Кроме того, если предполагается использование традиционной алгебраической модели вычислений (без косвенной адресации), можно доказать следующий, более слабый результат. | |||
Теорема 5. Пусть S – множество из n точек в пространстве Rd, а G = (S, E) – t-остов S для некоторой вещественной константы t > 1, имеющий m ребер. Используя алгебраическую модель вычислений, можно преобразовать граф G за время O(m log log n + nlog2 n) в структуру данных размера O(n log n), такую, что для любых двух точек p и q в S возможно вычислить за время O(log log n) (1 + ")-аппроксимацию расстояния по кратчайшему пути в G между p и q. | |||
== Применение == | |||