4551
правка
Декомпозиция на значительно удаленные пары: различия между версиями
Перейти к навигации
Перейти к поиску
Декомпозиция на значительно удаленные пары (посмотреть исходный код)
Версия от 12:01, 13 марта 2018
, 13 марта 2018→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 41: | Строка 41: | ||
== Основные результаты == | == Основные результаты == | ||
В работе [7] было показано, что для метрики, порожденной графом единичных дисков на n точках, и для любой константы c > | В работе [7] было показано, что для метрики, порожденной графом единичных дисков на n точках, и для любой константы <math>c \ge 1 \;</math> существует декомпозиция c-WSPD, содержащая O(n log n) пар, и такая декомпозиция может быть найдена за время O(n log n). Также было показано, что границы могут быть расширены на большее число размерностей. В следующих теоремах сведены основные результаты для двух и более размерностей. | ||
Теорема 1. Для любого множества точек S из n точек на плоскости и любой константы c > | '''Теорема 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 точек на плоскости в | '''Теорема 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>.''' | ||
| Строка 53: | Строка 53: | ||
Для множества точек с неограниченной плотностью применяется техника кластеризации, сходная с техникой из [6], в результате чего получается множество «центральных узлов» с ограниченной плотностью. После этого к множеству центральных узлов применяется алгоритм для множеств ограниченной плотности. Наконец, для получения декомпозиции значительно удаленных пар выполняется комбинация алгоритмов декомпозиции для множеств точек с ограниченной плотностью и для евклидовой метрики. Количество пар определяется количеством пар, построенных для множества константной плотности, которое, в свою очередь, определяется границей, полученной при помощи соображения об упаковке. Было показано, что граница количества пар является строгой для k > | Для множества точек с неограниченной плотностью применяется техника кластеризации, сходная с техникой из [6], в результате чего получается множество «центральных узлов» с ограниченной плотностью. После этого к множеству центральных узлов применяется алгоритм для множеств ограниченной плотности. Наконец, для получения декомпозиции значительно удаленных пар выполняется комбинация алгоритмов декомпозиции для множеств точек с ограниченной плотностью и для евклидовой метрики. Количество пар определяется количеством пар, построенных для множества константной плотности, которое, в свою очередь, определяется границей, полученной при помощи соображения об упаковке. Было показано, что граница количества пар является строгой для <math>k \ge 3 \;</math>. | ||
== Применение == | == Применение == | ||