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

Теорема 6. Пусть F – t-ограниченный набор многоугольных препятствий на плоскости с общей сложностью n, где t – положительная константа. Можно предварительно обработать набор F за время O(n log n), преобразовав его в структуру данных размера O(n log n), способную отвечать на запросы о длине <math>(1 + \varepsilon) \; </math>-аппроксимации кратчайшего пути, минующего препятствия, за время O(log n). Если точками запроса являются вершины F, ответы на запросы можно получить за время O(1).

Теорема 7. Пусть G = (S, E) – геометрический граф с n точек и m ребер, такой, что он является t-остовом S для некоторой константы t > 1. Граф G за время O(m + nlog n) может быть преобразован в структуру данных размера O(n log n), такую, что для заданного подмножества запроса S0 множества S возможно вычислить за время O(jS0jlogjS0j) <math>(1 + \varepsilon) \; </math>-аппроксимацию пары ближайших точек в S0 (расстояния измеряются по G).

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

Теорема 9. Пусть даны – геометрический граф с n точек и m ребер и константа C, являющаяся верхней границей протяженности t графа G. Тогда за время O(m + nlog n) возможно вычислить <math>(1 + \varepsilon) \; </math>-аппроксимацию t.