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

Остается открытым важный вопрос: в каких метрических пространствах допускается существование декомпозиций на значительно удаленные пары. Легко показать, что соображение об упаковке, использовавшееся для случая евклидова расстояния, можно распространить на случай с выпуклыми функциями расстояния в <math>\mathbb{R}^d</math>. Рассматривая более общую перспективу, Талвар [6] показал, как вычислять декомпозиции на значительно удаленные пары для множеств точек с ограниченными пропорциями в метрических пространствах с ограниченным удвоенным измерением.

С другой стороны, для метрики, порожденной графом дисков в пространстве <math>\mathbb{R}^2</math>, декомпозиция на значительно удаленные пары может потребовать квадратичного количества пар. (В графе дисков каждая точка <math>p \in S \;</math> является центром диска <math>D_p \;</math> радиуса <math>r_p \;</math>. Две точки p, q связаны ребром в том и только том случае, если <math>D_p \cap D_q \ne \empty</math>. Эта метрика определяется евклидовой длиной кратчайшего пути в полученном графе. Если граф представляет собой звезду с лучами идентичной длины, декомпозиция на значительно удаленные пары относительно коэффициента s > 4 должна состоять из пар одноэлементных множеств). Гао и Чжан [4] показали, что даже при использовании графа единичных дисков может потребоваться <math>\Omega(n^{2 - 2/d}) \;</math> пар для точек в пространстве <math>\mathbb{R}^d</math>.