Декомпозиция на значительно удаленные пары для графа единичных дисков: различия между версиями

В случае размерности d = 2 для решения этих задач обычно используется [[Voronoi diagram|диаграмма Вороного]]. Но для более высоких измерений намного практичнее использовать декомпозицию на значительно удаленные пары, поскольку сложность диаграммы Вороного для n точек может достигать <math>n^{\lfloor d/2 \rfloor} \;</math>.

Основным применением декомпозиции на значительно удаленные пары является построение достаточно хороших ''остовов'' для заданного множества точек S. [[T-Spanner|Остовом]] S с протяженностью t является геометрическая сеть N с множеством вершин S, такая, что для любых двух вершин <math>p, q \in S \;</math> евклидова длина кратчайшего пути, соединяющего p и q в N, не более чем в t раз превышает евклидово расстояние |pq|.

'''Теорема 4. Пусть S – множество из n точек в пространстве <math>\mathbb{R}^d</math> и t>1. Тогда остов S с протяженностью t, содержащий <math>O(s^d n) \;</math> ребер, можно построить за время <math>O(s^dn + n \; log \; n)</math>, где s = 4(t + 1)(t - 1).'''