4551
правка
Применение геометрических остовных сетей: различия между версиями
Перейти к навигации
Перейти к поиску
м
Применение геометрических остовных сетей (посмотреть исходный код)
Версия от 12:31, 28 октября 2016
, 28 октября 2016→Нотация и определения
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 12: | Строка 12: | ||
'''Задача 1 (оракул расстояния)'''. Пусть даны произвольная вещественная константа <math>\varepsilon > 0 \;</math> и геометрический граф G в d-мерном евклидовом пространстве с константной протяженностью t. Необходимо построить структуру данных, отвечающую на запросы об <math>(1 + \varepsilon) \; </math>-аппроксимации кратчайшего пути за константное время. | '''Задача 1 (оракул расстояния)'''. Пусть даны произвольная вещественная константа <math>\varepsilon > 0 \;</math> и геометрический граф G в d-мерном евклидовом пространстве с константной протяженностью t. Необходимо построить структуру данных, отвечающую на запросы об <math>(1 + \varepsilon) \; </math>-аппроксимации длины кратчайшего пути за константное время. | ||