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

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