В вычислительной геометрии задача о ближайшем соседе с фиксированным радиусом является вариантом задачи поиска ближайшего соседа . В задаче о ближайшем соседе с фиксированным радиусом в качестве входных данных дается набор точек в d -мерном евклидовом пространстве и фиксированное расстояние Δ. Необходимо разработать структуру данных, которая, учитывая точку запроса q , эффективно сообщает о точках структуры данных, которые находятся на расстоянии Δ от q . Проблема давно изучается; Бентли (1975) цитирует статью Левинталя 1966 года, в которой эта техника используется как часть системы визуализации молекулярных структур, и она имеет много других применений. [1]
Один из методов решения проблемы — округлить точки до целочисленной решетки , масштабированной так, чтобы расстояние между точками сетки было желаемым расстоянием Δ. Можно использовать хеш-таблицу для нахождения для каждой входной точки других входных данных, которые сопоставлены с близлежащими точками сетки, которые затем можно проверить на предмет того, находятся ли их неокругленные позиции на самом деле в пределах расстояния Δ. Количество пар точек, проверенных этой процедурой, и время процедуры линейно зависят от объединенного размера входных и выходных данных, когда размерность является фиксированной константой. Однако константа пропорциональности в линейной временной границе растет экспоненциально как функция размерности. [2] Используя этот метод, можно построить графики безразличия и графики единичного круга из геометрических данных за линейное время.
Современные параллельные методы для GPU способны эффективно вычислять все пары NNS фиксированного радиуса. Для конечных доменов метод Грина [3] показывает, что проблема может быть решена путем сортировки на равномерной сетке, нахождения всех соседей всех частиц за время O(kn), где k пропорционально среднему числу соседей. Хецлейн [4] улучшает это еще больше на современном оборудовании с помощью сортировки подсчетом и атомарных операций.
Проблема близких соседей с фиксированным радиусом возникает в непрерывных лагранжевых моделях (например, в гидродинамике сглаженных частиц), вычислительной геометрии и задачах точечных облаков (реконструкциях поверхностей).