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

== Ключевые слова и синонимы ==
Кластеризация

== Постановка задачи ==

'''Нотация'''

Пусть дано конечное множество точек A в пространстве <math>\mathbb{R}^d</math>. Назовем его ''ограничивающим прямоугольником'' R(A) d-мерный гиперпрямоугольник <math>[a_1, b_1] \times [a_2, b_2 ] \times ... \times [a_d, b_d] \;</math>, содержащий A и имеющий минимальную протяженность по каждому измерению.


Два множества точек A и B называются ''значительно удаленными'' относительно коэффициента удаленности s > 0, если существуют вещественное число r > 0 и две d-мерных сферы <math>C_A \;</math> и <math>C_B \;</math> радиуса r каждая, такие, что выполняются следующие соотношения.

1.	<math>C_A \cap C_B = \empty</math>

2.	<math>C_A \;</math> содержит ограничивающий прямоугольник R(A) множества A

3.	<math>C_B \;</math> содержит ограничивающий прямоугольник R(B) множества B

4.	<math>|C_A C_B| \ge s \cdot r</math>.


Здесь <math>|C_A C_B| \;</math> обозначает наименьшее евклидово расстояние между двумя точками в <math>C_A \;</math> и <math>C_B \;</math>, соответственно. Пример приведен на рис. 1. Пусть даны ограничивающие прямоугольники R(A)и R(B). Для проверки, являются ли множества A и B значительно удаленными относительно s, требуется всего O(d) времени.


[[Файл:WSPD_UDG.png]]

Рисунок 1. Множества A и B являются значительно удаленными относительно s


Две точки одного и того же множества, A или B, находятся друг от друга на евклидовом расстоянии, не более чем в 2/s превышающем возможное расстояние между любой парой точек <math>(a, b) \in A \times B \;</math>. Кроме того, разница расстояний между любыми такими парами (a, b), (a', b'), а именно |a – b|, |a' – b'| не может превышать 1 + 4/s.


Пусть дано множество S из n точек в пространстве <math>\mathbb{R}^d</math>. [[Декомпозиция на значительно удаленные пары|Декомпозицией S на значительно удаленные пары]] относительно коэффициента удаленности s является последовательность пар <math>(A_1, B_1), (A_2, B_2), ..., (A_m, B_m) \;</math>, такая, что

1.	<math>A_i, B_i \subset S \;</math> для i = 1...m

2.	<math>A_i \;</math> и <math>B_i \;</math> являются значительно удаленными относительно s для i = 1...m

3.	Для любых точек <math>a, b \in S, a \ne b \;</math>, существует уникальный индекс i в интервале 1...m, такой, что имеет место либо <math>a \in A_i \;</math> и <math>b \in B_i \;</math>, либо <math>b \in A_i \;</math> и a <math>\in B_i \;</math>.


Очевидно, что любое множество <math>S = \{ s_1, ..., s_n \} \;</math> содержит декомпозицию на значительно удаленные пары. Достаточно просто рассмотреть любые пары одноэлементных множеств <math>( \{ s_i \}, \{ s_j \}) \;</math>, где i < j. Вопрос заключается в том, существуют ли декомпозиции, состоящие из менее чем <math>O(n^2) \;</math> пар, и возможно ли их эффективно построить.

== Основные результаты ==
Следующий результат представили Кэллахан и Косарайю [1, 2].


'''Теорема 1. Пусть даны множество S из n точек в пространстве <math>\mathbb{R}^d</math> и коэффициент удаленности s, такой, что существует декомпозиция S на значительно удаленные пары относительно s, состоящая из <math>O(s^d d^{d/2} n) \;</math> пар вида <math>(A_i, B_i) \;</math>. Она может быть построена за время <math>O(d \; n \; log \; n + s^d d^{d/2+1} n)</math>.'''


Таким образом, если размерность d и коэффициент удаленности s фиксированы – что имеет место во многих случаях применения – то количество пар составляет O(n), а время вычисления декомпозиции – O(n log n).


Основным инструментом построения декомпозиции на значительно удаленные пары является [[split tree|расщепляемое дерево]] T(S) множества S. Корень r дерева T(S) содержит ограничивающий прямоугольник R(S) для S. Две его вершины-потомка получаются посредством разделения посередине по наибольшему измерению R(S) при помощи ортогональной гиперплоскости. Она разделяет S на два подмножества <math>S_a, S_b \;</math>, ограничивающие прямоугольники которых <math>R(S_a) \;</math> и <math>R(S_b) \;</math> хранятся в двух вершинах-потомках a и b корня r. Процесс повторяется до тех пор, пока в каждом подмножестве не останется только одна точка S. Эти одноэлементные множества образуют листья дерева T(S). Очевидно, что расщепляемое дерево T(S) содержит O(n) вершин. Оно не обязательно должно быть сбалансированным и может быть построено за время O(d n log n).


Декомпозицию S на значительно удаленные пары относительно заданного коэффициента удаленности s теперь можно получить из T(S) следующим образом. Для каждой внутренней вершины T(S) с потомками v и w вызывается следующая рекурсивная процедура FindPairs(v, w). Если <math>S_v \;</math> и <math>S_w \;</math> являются значительно удаленными, то процедура выдает результат <math>(S_v, S_w) \;</math>. В противном случае предположим, что наибольшее измерение <math>R(S_v) \;</math> превышает по длине наибольшее измерение <math>R(S_w) \;</math> и что <math>v_l, v_r \;</math> являются вершинами-потомками v в дереве T(S). После этого вызываются процедуры FindPairs(<math>v_l</math>, w) и FindPairs(<math>v_r</math>, w).


Общее количество вызовов процедуры ограничено количеством найденных значительно удаленных пар, которое, согласно соображению об упаковке, составляет <math>O(s^d d^{d/2} n) \;</math>. Однако совокупный размер всех множеств <math>A_i, B_i \;</math> в декомпозиции в общем случае является квадратичным относительно n.

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


'''Теорема 2. Пусть S – множество из n точек в пространстве <math>\mathbb{R}^d</math>. Тогда пара ближайших точек в S может быть найдена за оптимальное время O(n log n).'''


И в самом деле, пусть <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) пар, входящих в декомпозицию на значительно удаленные пары.


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


'''Теорема 3. Пусть S – множество из n точек в пространстве <math>\mathbb{R}^d</math>, и пусть <math>k \le n \;</math>. Тогда для каждой точки <math>p \in S \;</math> можно вычислить ''k'' ее ближайших соседей в S за совокупное время O(n log n + nk). В частности, для каждой точки S ее ближайшего соседа по S можно найти за оптимальное время O(n log n).'''


В случае размерности 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).'''


И в самом деле, если выбрать одно ребро <math>(a_i, b_i) \;</math> из каждой пары <math>(A_i, B_i) \;</math> декомпозиции S на значительно удаленные пары относительно s, то эти ребра формируют t-остов S, что можно показать по индукции по рангу каждой пары <math>(p, q) \in S^2 \;</math> в списке всех таких пар, отсортированном по расстоянию.

Остовы сами по себе имеют немало любопытных областей применения.

== Открытые вопросы ==
Остается открытым важный вопрос: в каких метрических пространствах допускается существование декомпозиций на значительно удаленные пары. Легко увидеть, что соображение об упаковке, использовавшееся для случая евклидова расстояния, можно распространить на случай с выпуклыми функциями расстояния в <math>\mathbb{R}^d</math>. Рассматривая более общую перспективу, Талвар [6] показал, как вычислять декомпозиции на значительно удаленные пары для множеств точек с ограниченными пропорциями в метрических пространствах с ограниченным дублирующим измерением.


С другой стороны, для метрики, порожденной графом дисков в пространстве <math>\mathbb{R}^2</math>, декомпозиция на значительно удаленные пары может потребовать квадратичного количества пар. (В графе дисков каждая точка <math>p \in S \;</math> является центром диска <math>D_p \;</math> радиуса <math>r_p \;</math>. Две точки <math>p, q \;</math> связаны ребром в том и только том случае, если <math>D_p \cap D_q \ne \empty</math>. Эта метрика определяется евклидовой длиной кратчайшего пути в полученном графе. Если граф представляет собой звезду с лучами идентичной длины, декомпозиция на значительно удаленные пары относительно коэффициента s > 4 должна состоять из пар одноэлементных множеств). Гао и Чжан [4] показали, что даже при использовании графа единичных дисков может потребоваться <math>\Omega(n^{2 - 2/d}) \;</math> пар для точек в пространстве <math>\mathbb{R}^d</math>.

== См. также ==
* [[Применение геометрических остовных сетей]]
* [[Геометрические остовы]]
* [[Планарные геометрические остовы]]

== Литература ==
1.	Callahan, P.: Dealing with Higher Dimensions: The Well-Separated Pair Decomposition and Its Applications. Ph.D. Thesis, The Johns Hopkins University, USA (1995)

2.	Callahan, P.B., Kosaraju, S.R.: A Decomposition of Multidimensional Point Sets with Applications to k-Nearest Neighbors and n-Body Potential Fields. J. ACM 42(1), 67-90 (1995)

3.	Eppstein, D.: Spanning Trees and Spanners. In: Sack, J.R., Urrutia, J. (eds.) Handbook of Computational Geometry, pp. 425-461. Elsevier, Amsterdam (1999)

4.	Ghao, J., Zhang, L.: Well-Separated Pair Decomposition for the Unit Disk Graph Metric and its Applications. SIAM J. Comput. 35(1),151-169(2005)

5.	Narasimhan, G., Smid, M.: Geometric Spanner Networks. Cambridge University Press, New York (2007)

6.	Talwar, K.: Bypassing the Embedding: Approximation Schemes and Compact Representations for Low Dimensional Metrics. In: Proceedings of the thirty-sixth Annual ACM Symposium on Theory of Computing (STOC'04), pp. 281-290 (2004)

[[Категория: Совместное определение связанных терминов]]