Применение геометрических остовных сетей: различия между версиями

Применение геометрических остовных сетей (посмотреть исходный код)

1279 байт добавлено , 11 октября 2016

4551

правка

@@ Строка 3: / Строка 3: @@
 == Постановка задачи ==
+Пусть дан геометрический граф в d-мерном пространстве. Было бы полезно предварительно обработать его таким образом, чтобы можно было эффективно отвечать на запросы о расстояниях (точно или приближенно). Алгоритмы, которые могут отвечать на запросы о расстояниях за константное время, называются также «оракулами расстояния». Очевидно, что при неограниченном времени и памяти для предварительной обработки легко можно построить точные оракулы расстояния. Далее будет рассмотрена разработка приближенных оракулов расстояния при ограниченных значениях времени и памяти для предварительной обработки для семейства геометрических графов с константной протяженностью.
+== Нотация и определения ==