4551
правка
Применение геометрических остовных сетей: различия между версиями
Перейти к навигации
Перейти к поиску
Применение геометрических остовных сетей (посмотреть исходный код)
Версия от 23:24, 15 октября 2016
, 15 октября 2016→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 52: | Строка 52: | ||
'''Группировка''' | '''Группировка''' | ||
Поскольку предполагаемая в данном случае вычислительная модель не допускает использования функций типа «пол», важным компонентом алгоритма является «инструмент группировки», позволяющий, после соответствующей предварительной обработки, за константное время вычислять величину под названием BINDEX, обозначающую округление до целого числа в меньшую сторону логарифма расстояния между любой парой входных точек. | |||
Теорема 3. Пусть S – множество из n точек в пространстве Rd, содержащихся в гиперкубе (0; nk)d для некоторой положительной целочисленной константы k, а " – положительная вещественная константа. Множество S за время O(n log n) может быть преобразовано в структуру данных размера O(n), такую, что для любых двух точек p и q в S, |pq| > 1, возможно вычислить за константное время величину BIndex "(p, q) = blog1+" |pq|c. | |||
Упомянутое в теореме 3 вычисление за константное время осуществляется посредством сведения задачи к задаче нахождения ответов на запросы о наименьшем общем предке для пар вершин дерева, для которой Бендер и Фарах-Колтон недавно предложили решение с константным временем выполнения [4]. | |||
== Основные результаты == | |||