Применение геометрических остовных сетей: различия между версиями

Используя инструменты группировки и усечения, а также алгоритмы Гудмундссона и др. можно доказать следующую теорему.

Теорема 4. Пусть t > 1 и " > 0 – вещественные константы. Пусть 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 и ".

Теорема 5. Пусть S – множество из n точек в пространстве <math>\mathbb{R}^d \;</math>, а 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) <math>(1 + \varepsilon) \; </math>-аппроксимацию расстояния по кратчайшему пути в G между p и q.