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

В работе [7] было показано, что для метрики, порожденной графом единичных дисков на n точках, и для любой константы <math>c \ge 1 \;</math> существует декомпозиция c-WSPD, содержащая O(n log n) пар, и такая декомпозиция может быть найдена за время O(n log n). Также было показано, что границы могут быть расширены на большее число размерностей. В следующих теоремах сведены основные результаты для двух и более размерностей.

'''Теорема 1. Для любого множества точек S из n точек на плоскости и любой константы <math>c \ge 1 \;</math> существует декомпозиция <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> существует декомпозиция <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>.'''