4551
правка
Применение геометрических остовных сетей: различия между версиями
Перейти к навигации
Перейти к поиску
Применение геометрических остовных сетей (посмотреть исходный код)
Версия от 15:32, 17 октября 2016
, 17 октября 2016→Применение
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 73: | Строка 73: | ||
== Применение == | == Применение == | ||
Как упоминалось ранее, вышеописанная структура данных может быть применена к некоторым другим задачам. Во-первых, это поиск ответов на запросы о расстоянии для планарной области с препятствиями в виде многоугольников. Более того, область к тому же должна быть t- | Как упоминалось ранее, вышеописанная структура данных может быть применена к некоторым другим задачам. Во-первых, это поиск ответов на запросы о расстоянии для планарной области с препятствиями в виде многоугольников. Более того, область к тому же должна быть t-ограниченной, что означает, что длина кратчайшего пути, огибающего препятствия, между любыми двумя точками входного множества, не более чем в t раз превышает евклидово расстояние между ними. Иными словами, граф видимости должен быть t-остовом входного множества точек. | ||
Теорема 6. Пусть F – t-ограниченный набор многоугольных препятствий на плоскости с общей сложностью n, где t – положительная константа. Можно предварительно обработать набор F за время O(n log n), преобразовав его в структуру данных размера O(n log n), способную отвечать на запросы о длине (1 + ")-аппроксимации кратчайшего пути, минующего препятствия, за время O(log n). Если точками запроса являются вершины F, ответы на запросы можно получить за время O(1). | |||
Вторым вариантом применения структуры данных оракула расстояния являются версии запросов из задач о вычислении пары ближайших точек, где запросы ограничены определенными подмножествами входного множества. | |||