En geometría computacional , el problema de vecino cercano de radio fijo es una variante del problema de búsqueda de vecino más cercano . En el problema del vecino cercano de radio fijo, se da como entrada un conjunto de puntos en el espacio euclidiano d- dimensional y una distancia fija Δ. Se debe diseñar una estructura de datos que, dado un punto de consulta q , informe de manera eficiente los puntos de la estructura de datos que están dentro de la distancia Δ de q . El problema se ha estudiado durante mucho tiempo; Bentley (1975) cita un artículo de 1966 de Levinthal que utiliza esta técnica como parte de un sistema para visualizar estructuras moleculares y tiene muchas otras aplicaciones. [1]
Solución mediante redondeo y hash
Un método para resolver el problema es redondear los puntos a un entramado entero , escalado de modo que la distancia entre los puntos de la cuadrícula sea la distancia deseada Δ. Se puede usar una tabla hash para encontrar, para cada punto de entrada, las otras entradas que se asignan a puntos de cuadrícula cercanos, que luego se pueden probar para ver si sus posiciones no redondeadas están realmente dentro de la distancia Δ. El número de pares de puntos probados por este procedimiento, y el tiempo para el procedimiento, es lineal en el tamaño combinado de entrada y salida cuando la dimensión es una constante fija. Sin embargo, la constante de proporcionalidad en el límite de tiempo lineal crece exponencialmente en función de la dimensión. [2] Con este método, es posible construir gráficos de indiferencia y gráficos de disco unitario a partir de datos geométricos en tiempo lineal.
Otras soluciones
Los métodos paralelos modernos para GPU pueden calcular de manera eficiente todos los pares NNS de radio fijo. Para dominios finitos, el método de Green [3] muestra que el problema se puede resolver clasificando en una cuadrícula uniforme, encontrando todos los vecinos de todas las partículas en el tiempo O (kn), donde k es proporcional al número promedio de vecinos. Hoetzlein [4] mejora esto aún más en el hardware moderno con operaciones atómicas y de clasificación por conteo.
Aplicaciones
El problema de los vecinos cercanos de radio fijo surge en simulaciones lagrangianas continuas (como la hidrodinámica de partículas suavizadas), geometría computacional y problemas de nubes de puntos (reconstrucciones de superficies).
Ver también
Referencias
- ^ Bentley, Jon Louis (1975), Un estudio de técnicas para la búsqueda de vecino cercano de radio fijo (PDF) , Informe técnico SLAC-186 y STAN-CS-75-513, Stanford Linear Accelerator Center.
- ^ Bentley, Jon L .; Stanat, Donald F .; Williams, E. Hollins, Jr. (1977), "La complejidad de encontrar vecinos cercanos de radio fijo", Information Processing Letters , 6 (6): 209–212, doi : 10.1016 / 0020-0190 (77) 90070-9 , MR 0489084.
- ^ Green, Simon (2012), Partículas CUDA (PDF)
- ^ Hoetzlein, Rama (2014), "Vecinos más cercanos rápidos de radio fijo: Fluidos interactivos de millones de partículas" (PDF) , Conferencia de tecnología de GPU