4551
правка
Применение геометрических остовных сетей: различия между версиями
Перейти к навигации
Перейти к поиску
м
Применение геометрических остовных сетей (посмотреть исходный код)
Версия от 12:54, 28 октября 2016
, 28 октября 2016→Применение
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) м (→Применение) |
||
| Строка 91: | Строка 91: | ||
'''Теорема 8. Пусть G = (S, E) – геометрический граф с n точек и m ребер, такой, что он является t-остовом S для некоторой константы t > 1. Граф G за время O(m + nlog n) может быть преобразован в структуру данных размера O(n log n), такую, что для двух непересекающихся подмножеств запроса X и Y множества S возможно вычислить за время O((|X| + |Y|)log(|X| + |Y|)) <math>(1 + \varepsilon) \; </math>-аппроксимацию бихроматической пары ближайших точек (расстояния измеряются по G).''' | '''Теорема 8. Пусть G = (S, E) – геометрический граф с n точек и m ребер, такой, что он является t-остовом S для некоторой константы t > 1. Граф G за время O(m + nlog n) может быть преобразован в структуру данных размера O(n log n), такую, что для двух непересекающихся подмножеств запроса X и Y множества S возможно вычислить за время O((|X| + |Y|) log(|X| + |Y|)) <math>(1 + \varepsilon) \; </math>-аппроксимацию бихроматической пары ближайших точек (расстояния измеряются по G).''' | ||