4551
правка
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
Строка 50: | Строка 50: | ||
Сложность получения декомпозиции значительно удаленных пар под метрикой на графе единичных дисков заключается в том, что две точки, расположенные близко друг к другу в пространстве, необязательно являются близкими в графовой метрике. Вышеприведенные границы вначале были продемонстрированы для множества точек с плотностью, ограниченной некоторой | Сложность получения декомпозиции значительно удаленных пар под метрикой на графе единичных дисков заключается в том, что две точки, расположенные близко друг к другу в пространстве, необязательно являются близкими в графовой метрике. Вышеприведенные границы вначале были продемонстрированы для множества точек с плотностью, ограниченной некоторой константой – т.е. множества, в котором любой единичный диск покрывает только константное число точек множества. Верхняя граница количества пар вычисляется при помощи соображения об упаковке, аналогичного приведенному в работе [8]. | ||
правка