4551
правка
Применение геометрических остовных сетей: различия между версиями
Перейти к навигации
Перейти к поиску
Применение геометрических остовных сетей (посмотреть исходный код)
Версия от 12:11, 28 октября 2016
, 28 октября 2016→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 28: | Строка 28: | ||
'''Усечение''' | '''Усечение''' | ||
Если у входной геометрической сети сверхлинейное количество ребер, то этап предварительной обработки структуры данных оракула расстояния эффективно «усекает» сеть таким образом, чтобы количество ребер стало линейным. В результате усечения протяженность остова может немного увеличиться. Нижеследующую теорему доказали Гудмундссон и др. [12]. | Если у входной геометрической сети сверхлинейное количество ребер, то этап предварительной обработки структуры данных оракула расстояния эффективно «усекает» сеть таким образом, чтобы количество ребер стало линейным. В результате усечения протяженность остова может немного увеличиться. Нижеследующую теорему доказали Гудмундссон и др. [12]. | ||
| Строка 52: | Строка 53: | ||
'''Группировка''' | '''Группировка''' | ||
Поскольку предполагаемая в данном случае вычислительная модель не допускает использования функций типа «пол», важным компонентом алгоритма является «инструмент группировки», позволяющий, после соответствующей предварительной обработки, за константное время вычислять величину под названием BINDEX, обозначающую округление до целого числа в меньшую сторону логарифма расстояния между любой парой входных точек. | Поскольку предполагаемая в данном случае вычислительная модель не допускает использования функций типа «пол», важным компонентом алгоритма является «инструмент группировки», позволяющий, после соответствующей предварительной обработки, за константное время вычислять величину под названием BINDEX, обозначающую округление до целого числа в меньшую сторону логарифма расстояния между любой парой входных точек. | ||
Теорема 3. Пусть S – множество из n точек в пространстве <math>\mathbb{R}^d \;</math>, содержащихся в гиперкубе (0 | Теорема 3. Пусть S – множество из n точек в пространстве <math>\mathbb{R}^d \;</math>, содержащихся в гиперкубе <math>(0, n^k)^d \;</math> для некоторой положительной целочисленной константы k, а <math>\varepsilon \;</math> – положительная вещественная константа. Множество S за время O(n log n) может быть преобразовано в структуру данных размера O(n), такую, что для любых двух точек p и q в S, <math>|pq| \ge 1 \;</math>, возможно вычислить за константное время величину <math>BIndex_{ \varepsilon} (p, q) = \lfloor log_{1 + \varepsilon} \; |pq| \rfloor</math>. | ||