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

'''Теорема 1. Для любого множества точек S из n точек на плоскости и любого <math>c \ge 1 \;</math> существует вышеописанная c-WSPD-декомпозиция <math>\mathcal{P}</math> множества S под метрикой на графе единичных дисков, такая, что <math>\mathcal{P}</math> содержит <math>O(c^4 \; n \; log \; n)</math> пар и может быть вычислена за время <math>O(c^4 \; n \; log \; n)</math>.'''

'''Теорема 2. Для любого множества точек S из n точек на плоскости в <math>\mathbb{R}^k</math> для <math>k \ge 3 \;</math> и любой константы <math>c \ge 1 \;</math> существует c-WSPD-декомпозиция <math>\mathcal{P}</math> множества S под метрикой на графе единичных кругов, такая, что <math>\mathcal{P}</math> содержит <math>O(n^{2 - 2/k}) \;</math> пар и может быть вычислена за время <math>O(n^{4/3} \; polylog \; n)</math> для k = 3 и за время <math>O(n^{2 - 2/k}) \;</math> для <math>k \ge 4 \;</math>.'''

Для множества точек с неограниченной плотностью применяется техника кластеризации, сходная с техникой из [6], в результате чего получается множество «центральных узлов» с ограниченной плотностью. После этого к множеству центральных узлов применяется алгоритм для множеств ограниченной плотности. Наконец, для получения декомпозиции на значительно удаленные пары выполняется комбинация алгоритмов декомпозиции для множеств точек с ограниченной плотностью и для евклидовой метрики. Количество пар определяется количеством пар, построенных для множества константной плотности, которое, в свою очередь, определяется границей, полученной при помощи соображения об упаковке. Было показано, что граница количества пар является строгой для <math>k \ge 3 \;</math>.