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

Ключевые слова и синонимы

Кластеризация

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

Нотация

Пусть дано конечное множество точек A в пространстве [math]\displaystyle{ \mathbb{R}^d }[/math]. Назовем его ограничивающим прямоугольником R(A) d-мерный гиперпрямоугольник [math]\displaystyle{ [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]\displaystyle{ C_A \; }[/math] и [math]\displaystyle{ C_B \; }[/math] радиуса r каждая, такие, что выполняются следующие соотношения.

1. [math]\displaystyle{ C_A \cap C_B = \empty }[/math]

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

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

4. [math]\displaystyle{ |C_A C_B| \ge s \cdot r }[/math].

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

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

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

1. [math]\displaystyle{ A_i, B_i \subset S \; }[/math] для i = 1, ..., m

2. [math]\displaystyle{ A_i \; }[/math] и [math]\displaystyle{ B_i \; }[/math] являются значительно удаленными относительно s для i = l, ..., m

3. Для любых точек [math]\displaystyle{ a, b \in S, a \ne b \; }[/math], существует уникальный индекс i в интервале 1, ..., m, такой, что имеет место либо a 2 Ai и b 2 Bi, либо b 2 Ai и a 2 Bi.

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