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

Определение декомпозиции на значительно удаленные пары может быть естественным образом расширено на любое метрическое пространство. Однако в метрических пространствах общего вида декомпозиция на значительно удаленные пары с размером ниже квадратичного может оказаться невозможной. И в самом деле, для метрики, порожденной звездчатым деревом с единичным весом каждого ребра 1, любая декомпозиция на значительно удаленные пары требует квадратичного числа пар. По этой причине для подобной метрики она не имеет практического смысла. Тем не менее, было показано, что для метрики на основе графов единичных дисков существуют алгоритмы декомпозиции на значительно удаленные пары с близким к линейному размером и, следовательно, многие задачи о близости на базе этой метрики могут быть эффективно решены при помощи этого подхода.

1 Метрика, порожденная графом (с положительными весами ребер), представляет собой метрику на основе кратчайшего пути по графу.