Búsqueda de vecino más cercano con condiciones de contorno periódicas

Question

En una caja cúbica, tengo una gran colección de puntos en R^3. Me gustaría encontrar los k vecinos más cercanos para cada punto. Normalmente pienso usar algo así como un árbol k-d, pero en este caso tengo condiciones de contorno periódicas. Según lo entiendo, un árbol k-d funciona al dividir el espacio cortándolo en hiperplanos de una dimensión menos, es decir, en 3D dividiríamos el espacio dibujando planos en 2D. Para cualquier punto dado, está en el plano, encima o debajo de él. Sin embargo, cuando divide el espacio con condiciones de contorno periódicas, ¡se puede considerar que un punto está en cualquier lado!

¿Cuál es el método más eficaz de encontrar y mantener una lista de vecinos más cercanos con condiciones de contorno periódicas en R^3?

Las aproximaciones no son suficientes, y los puntos solo se moverán uno a la vez (piense en la simulación de Monte Carlo no en N-cuerpos).

Answer 1

Incluso en el caso de Euclides, un punto y su vecino más cercano puede estar en lados opuestos de un hiperplano. El núcleo de la búsqueda del vecino más cercano en un árbol k-d es un primitivo que determina la distancia entre un punto y un cuadro; la única modificación necesaria para su caso es tener en cuenta la posibilidad de envolvente.

Como alternativa, puede poner en práctica los árboles de la cubierta, que funcionan en cualquier métrica.

Answer 2

(les dejo esta respuesta, aunque no estoy totalmente seguro de que funciona. Intuitivamente parece bien, pero podría ser un caso extremo no he considerado)

Si está trabajando con las condiciones de contorno periódicas, entonces se puede pensar que el espacio se corta en una serie de bloques de un tamaño fijo que luego se superponen uno encima del otro. Supongamos que estamos en R . Entonces, una opción sería replicar ese bloque nueve veces y colocarlo en una cuadrícula de 3x3 de duplicados del bloque. Teniendo en cuenta esto, si nos encontramos con el vecino más cercano de cualquier nodo individual en la plaza central, a continuación, ya sea

1. El vecino más cercano es el interior de la plaza central, en cuyo caso el vecino es un vecino más cercano, o
2. El el vecino más cercano está en un cuadrado que no sea el cuadrado central. En ese caso, si encontramos el punto en el cuadrado central al que corresponde el vecino, ese punto debe ser el vecino más cercano al punto de prueba original bajo la condición de frontera periódica.

En otras palabras, simplemente replicamos los elementos suficientes veces para que la distancia euclidiana entre los puntos nos permita encontrar la distancia correspondiente en el espacio del módulo.

En n dimensiones, lo que tendría que hacer 3 ⁿ copias de todos los puntos, que suena como mucho, pero para R es sólo un aumento 27x sobre el tamaño de los datos originales. Esto es sin duda un gran aumento, pero si está dentro de los límites aceptables, debería poder utilizar este truco para aprovechar un árbol kd estándar (u otro árbol espacial).

Espero que esto ayude! (¡Y espero que esto sea correcto!)