Декомпозиция на значительно удаленные пары для графа единичных дисков
Ключевые слова и синонимы
Кластеризация
Постановка задачи
Нотация
Пусть дано конечное множество точек A в пространстве Rd. Назовем его ограничивающим прямоугольником bounding box R(A) d-мерный гиперпрямоугольник [a1, b1] x [a2, b2 ] ... x [ad, bd], содержащий A и имеющий минимальную протяженность по каждому измерению. Два множества точек A и B называются значительно удаленными относительно коэффициента удаленности s > 0, если существуют вещественное число r > 0 и две d-мерных сферы CA и CB радиуса r каждая, такие, что выполняются следующие соотношения.
1. CA \ CB = ;
2. CA содержит ограничивающий прямоугольник R(A) множества A
3. CB содержит ограничивающий прямоугольник R(B) множества B
4. \CACB\ >w.
Здесь |CACB| обозначает наименьшее евклидово расстояние между двумя точками в CA и CB, соответственно. Пример приведен на рис. 1. Пусть даны ограничивающие прямоугольники R(A)и R(B). Для проверки, являются ли множества A и B значительно удаленными относительно s, требуется всего O(d) времени.
Две точки одного и того же множества, A или B, находятся друг от друга на евклидовом расстоянии, не более чем в 2/s превышающем возможное расстояние между любой парой точек (a, b) 2 A x B. Кроме того, разница расстояний между любыми такими парами (a, b); (a0, b0), |a – b|, |a’ – b’| не может превышать 1 + 4/s.
Пусть дано множество S из n точек в пространстве Rd. Декомпозицией S на значительно удаленные пары относительно коэффициента удаленности s является последовательность пар (A1, B1), (A2, B2), …, (Am, Bm), такая, что
1. Ai, Bi С S для i = 1, …, m
2. Ai и Bi являются значительно удаленными относительно s для i = l, …, m
3. Для всех точек любых a, b 2 S, a / b, существует уникальный индекс i в интервале 1, …, m, такой, что имеет место a 2 Ai и b 2 Bi, либо b 2 Ai и a 2 Bi.
Очевидно, что любое множество S = fs 1, …, .sng содержит декомпозицию на значительно удаленные пары. Достаточно просто рассмотреть любые пары одноэлементных множеств (FSIG, FSJG), где i < j. Вопрос заключается в том, существуют ли декомпозиции, состоящие из менее чем O(n2) пар, и можно ли их эффективно построить.