4430
правок
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) м (→См. также) |
||
(не показаны 3 промежуточные версии этого же участника) | |||
Строка 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).''' | ||
Строка 97: | Строка 97: | ||
'''Теорема 9. Пусть даны | '''Теорема 9. Пусть даны геометрический граф с n точек и m ребер и константа C, являющаяся верхней границей протяженности t графа G. Тогда за время O(m + nlog n) возможно вычислить <math>(1 + \varepsilon) \; </math>-аппроксимацию t.''' | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Строка 107: | Строка 107: | ||
== См. также == | == См. также == | ||
* | * [[Алгоритм поиска кратчайших путей между всеми парами в разреженных графах]] | ||
* | * [[Алгоритм поиска кратчайших путей между всеми парами при помощи матричного произведения]] | ||
* | * [[Геометрические остовы]] | ||
* | * [[Планарные геометрические остовы]] | ||
* | * [[Разреженные остовы графов]] | ||
* | * [[Синхронизаторы и остовы]] | ||
== Литература == | == Литература == |
правок