Delaunay triangulations for moving points fixed radius near neighbors

Abstract

En simulaciones de fluidos basadas en el método smoothed particle hydrodynamics (SPH), la operación para encontrar los vecinos dado un cierto umbral fijo de cada partícula es la operación más costosa que debe realizarse en cada iteración de la simulación. A este problema lo llamamos Moving Points Fixed Radius Nearest Neighbors (MPFRNN). El mismo problema, cuando las partículas no se mueven, se llama Fixed Radius Nearest Neighbors (FRNN). El principal aporte de este trabajo es la descripción y evaluación en escenarios de simulación sin preservar el volumen excluido de cada partícula (donde las partículas pueden atravesarse entre sí), de un algoritmo nuevo que resuelve el problema MPFRNN mediante triangulaciones de Delaunay. El análisis teórico sugiere que este enfoque es más rápido que las soluciones del estado del arte dadas ciertas condiciones. Este trabajo también explora las dificultades de paralelizar este algoritmo en la GPU.

En el algoritmo secuencial descrito, la triangulación de Delaunay inicial se construye a partir de un conjunto de $n$ vértices utilizando el algoritmo Jump&Walk. Luego, se mantiene eliminando y luego moviendo y reinsertando todos los vértices en la triangulación. Esto se mejora en el caso de los vértices que no se mueven fuera de sus cavidades (que es el polígono formado por los vértices alrededor de un vértice), puesto que la triangulación se puede arreglar localmente mediante flips. Finalmente, el FRNN se calcula realizando una búsqueda en profundidad (DFS) en la triangulación, teniendo especial consideración en no realizar cálculos de distancia duplicados, utilizando sólo O(n) memoria adicional.

Los datos experimentales muestran que el algoritmo secuencial propuesto es más lento que un algoritmo de referencia en la mayoría de los escenarios probados. Aún así, el algoritmo propuesto tiene un tiempo de actualización comparable, que corresponde al tiempo que lleva actualizar la triangulación de Delaunay de los puntos móviles. Esto se puede utilizar en trabajos futuros para desarrollar una mejor estructura de datos secuenciales para resolver el problema MPFRNN.