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

Согласно определению в [3], для любых двух множеств A и B множество пар <math>\mathcal{P} = \{ P_1, P_2, ..., P_m \} \;</math>, где <math>P_i = (A_i, B_i) \;</math>, называется попарной [[Decomposition|декомпозицией]] (A, B) (или A, если A = B) в случае, если:

• для всех значений индексов i верно <math>A_i \subseteq A , B_i \subseteq B</math>;

• <math>A_i \cap B_i = \empty</math>;

• для любых двух элементов <math>a \in A, b \in B \;</math> существует уникальный индекс i, такой, что <math>a \in A_i, b \in B_i \;</math>. Будем говорить, что (a, b) ''покрыты'' парой <math>(A_i, B_i) \;</math>.

Если при этом каждая пара в <math>\mathcal{P}</math> является значительно удаленной с коэффициентом c, <math>\mathcal{P}</math> называется ''декомпозицией на значительно удаленные пары с коэффициентом c'' (или, для краткости, c-WSPD). Очевидно, что любое метрическое пространство поддерживает c-WSPD квадратичного размера в виде тривиального семейства, содержащего все попарные комбинации элементов.