Фиксированный радиус рядом с соседями
В вычислительной геометрии является задача ближайшего соседа с фиксированным радиусом вариантом задачи поиска ближайшего соседа . В задаче о ближайшем соседе с фиксированным радиусом в качестве входных данных задается набор точек в d -мерном евклидовом пространстве и фиксированное расстояние Δ. Необходимо спроектировать структуру данных, которая по заданной точке запроса q эффективно сообщает о точках структуры данных, находящихся на расстоянии Δ от q . Проблема давно изучена; Бентли (1975) цитирует статью Левинталя 1966 года, в которой этот метод используется как часть системы визуализации молекулярных структур, и он имеет множество других применений. [1]
Решение округлением и хешированием
[ редактировать ]Одним из методов решения проблемы является округление точек до целочисленной решетки , масштабированной так, чтобы расстояние между точками сетки было желаемым расстоянием Δ. Хэш -таблицу можно использовать для поиска для каждой входной точки других входных данных, которые сопоставлены с соседними точками сетки, которые затем можно проверить на предмет того, действительно ли их неокругленные позиции находятся в пределах расстояния Δ. Количество пар точек, проверяемых этой процедурой, и время процедуры линейны в зависимости от объединенного входного и выходного размера, когда размерность является фиксированной константой. Однако константа пропорциональности в линейном времени растет экспоненциально в зависимости от размерности. [2] Используя этот метод, можно построить графики безразличия и графы единичного диска на основе геометрических данных за линейное время.
Другие решения
[ редактировать ]Современные параллельные методы для графических процессоров способны эффективно вычислять все пары NNS фиксированного радиуса. Для конечных областей метод Грина [3] показывает, что проблему можно решить путем сортировки на однородной сетке и поиска всех соседей всех частиц за время O(kn), где k пропорционально среднему числу соседей. Хетцляйн [4] улучшает это на современном оборудовании с помощью сортировки подсчета и атомарных операций.
Приложения
[ редактировать ]Проблема фиксированного радиуса вблизи соседей возникает в непрерывном лагранжевом моделировании (например, гидродинамике сглаженных частиц), вычислительной геометрии и задачах облака точек (реконструкция поверхности).
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Бентли, Джон Луи (1975), Обзор методов поиска ближних соседей с фиксированным радиусом (PDF) , Технический отчет SLAC-186 и STAN-CS-75-513, Стэнфордский центр линейных ускорителей .
- ^ Бентли, Джон Л .; Станат, Дональд Ф.; Уильямс, Э. Холлинз-младший (1977), «Сложность поиска ближайших соседей с фиксированным радиусом», Information Processing Letters , 6 (6): 209–212, doi : 10.1016/0020-0190(77)90070-9 , МР 0489084 .
- ^ Грин, Саймон (2012), Частицы CUDA (PDF)
- ^ Хетцляйн, Рама (2014), «Быстрые ближайшие соседи с фиксированным радиусом: интерактивные жидкости с миллионом частиц» (PDF) , Конференция по технологиям графических процессоров