En geometría computacional , el problema del vecino cercano de radio fijo es una variante del problema de búsqueda del vecino más próximo . En el problema del vecino cercano de radio fijo, se proporciona como entrada un conjunto de puntos en un espacio euclidiano de dimensión d 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 ha sido 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]
Un método para resolver el problema es redondear los puntos a una red entera , escalada de modo que la distancia entre los puntos de la cuadrícula sea la distancia deseada Δ. Se puede utilizar 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 Δ. La cantidad 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 como una función de la dimensión. [2] Usando 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.
Los métodos paralelos modernos para GPU son capaces de calcular de manera eficiente todos los pares de NNS de radio fijo. Para dominios finitos, el método de Green [3] muestra que el problema puede resolverse ordenando en una cuadrícula uniforme, encontrando todos los vecinos de todas las partículas en tiempo O(kn), donde k es proporcional al número promedio de vecinos. Hoetzlein [4] mejora esto aún más en hardware moderno con operaciones atómicas y de ordenamiento por conteo.
El problema de los vecinos cercanos de radio fijo surge en simulaciones lagrangianas continuas (como la hidrodinámica de partículas suavizadas), la geometría computacional y los problemas de nubes de puntos (reconstrucciones de superficies).