4551
правка
Применение геометрических остовных сетей: различия между версиями
Перейти к навигации
Перейти к поиску
м
Применение геометрических остовных сетей (посмотреть исходный код)
Версия от 12:12, 28 октября 2016
, 28 октября 2016→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 57: | Строка 57: | ||
Теорема 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>. | '''Теорема 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>.''' | ||