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

Две точки одного и того же множества, 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 = l, ..., m

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