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