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

Далее размерность d будет считаться константной. Декомпозиция на значительно удаленные пары может эффективно применяться для решения задач о близости на в пространстве <math>\mathbb{R}^d</math>.

И в самом деле, пусть <math>q \in S \;</math> – ближайший сосед точки <math>p \in S \;</math>. Можно построить декомпозицию S на значительно удаленные пары относительно коэффициента удаленности s > 2 за время O(n log n). Пусть <math>(A_i, B_i) \;</math> – пара, в которой <math>p \in A_i \;</math> и <math>q \in B_i \;</math>. Если бы в <math>A_i \;</math> имелась другая точка <math>p' \;</math> из множества S, имело бы место соотношение <math>|pp'| \le 2/s \cdot |pq| < |pq|</math>, что невозможно. Следовательно, <math>A_i \;</math> является одноэлементным множеством. Если (p, q) является парой ближайших точек в S, то множество <math>B_i \;</math> тоже должно быть одноэлементным. Таким образом, пару ближайших точек можно найти посредством рассмотрения всех пар одноэлементных множеств среди O(n) пар, входящих в декомпозицию на значительно удаленные пары.

При помощи следующих действий можно получить более обобщенный результат.

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