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

Обозначим за d(<math>\cdot, \cdot</math>) евклидову метрику. Для множества точек S на плоскости графом единичных дисков I(S) = (S, E) является взвешенный граф, для которого ребро e = (p, q) принадлежит графу, если <math>d(p, q) \le 1 \;</math>, а вес ребра e равен d(p, q). Аналогичным образом можно определить граф единичных шаров для точек в пространстве более высокой размерности.

Рассмотрим метрическое пространство <math>(S, \pi) \;</math>, где <math>S \;</math> – множество элементов, а <math>\pi \;</math> – функция расстояния, определенная на <math>S \times S \;</math>. Для любого подмножества <math>S_1 \subseteq S \;</math> [[диаметр]] <math>D_{\pi}(S_1) \;</math> (или <math>D(S_1) \;</math>, если <math>\pi \;</math> очевидно из контекста) множества <math>S \;</math> определяется как <math>max_{s_1, s_2 \in S_1} \; \pi (s_1, s_2)</math>. ''Расстояние'' <math>\pi(S_1, S_2) \;</math> между двумя множествами <math>S_1, S_2 \subseteq S \;</math> определяется как <math>max_{s_1 \in S_1, s_2 \in S_2} \; \pi (s_1, s_2)</math>.