4488
правок
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
Строка 23: | Строка 23: | ||
Две точки одного и того же множества, A или B, находятся друг от друга на евклидовом расстоянии, не более чем в 2/s превышающем возможное расстояние между любой парой точек (a, b) | Две точки одного и того же множества, 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 точек в пространстве | Пусть дано множество S из n точек в пространстве <math>\mathbb{R}^d</math>. [[Декомпозиция на значительно удаленные пары|Декомпозицией S на значительно удаленные пары]] относительно коэффициента удаленности s является последовательность пар <math>(A_1, B_1), (A_2, B_2), ..., (A_m, B_m) \;</math>, такая, что | ||
1. | 1. <math>A_i, B_i \subset S \;</math> для i = 1, ..., m | ||
2. | 2. <math>A_i \;</math> и <math>B_i \;</math> являются значительно удаленными относительно s для i = l, ..., m | ||
3. Для | 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. | ||
правок