Для заданного набора точек и радиуса . Что представляет собой сложность поиска точки с большим числом точек на расстоянии, меньшем, чем . Например, тот, который максимизирует ?
Алгоритм грубой силы будет проходить через каждую точку и подсчитывать количество точек, которые находятся на расстоянии, меньшем, чем . Это дало бы сложность .
Есть ли лучший подход?
ball
из заголовка должен быть из набора?) Одна идея может состоять в том, чтобы оценить, является ли радиус небольшим по сравнению со средним расстоянием до ближайшего соседа или порядка диаметра (и рассмотреть подходы для этих крайностей (плоскость для малогоОтветы:
Похоже, что сублинейный алгоритм для задачи подсчета дальности мяча пока неизвестен.
Однако, если вы могли бы принять неточный ответ, то вы могли бы аппроксимировать диск набором квадратов с различной ориентацией. Для каждой ориентации вам нужно построить Range Range , который позволит вам подсчитать все точки внутри квадрата за время (k - количество результирующих точек).O(log2(n)+k)
Каждое дерево диапазона потребует памяти, чем лучше вы хотите приблизить, тем больше ориентаций вы должны использовать. Например, две ориентации дадут вам восьмиугольник , который приближает диск с ошибкой площади менее 6%.O(n⋅log(n))
источник
Ответ не так прост, есть углубленное изучение этого вопроса в теории сложности; это, кажется, изучается, например, как следующая проблема, которая сосредоточена вокруг быстрых запросов «подсчета сферического диапазона». Да, улучшенные теоретические границы возможны, но это, кажется, абстрактные алгоритмы, которые никто не реализовывал. Если вам нужны реальные реализации, это другой вопрос.
источник