En la mayoría de las implementaciones (¿todas?) Del Método rápido multipolar (FMM), se utilizan octrees para descomponer el dominio relevante. Teóricamente, los octrees proporcionan un límite volumétrico simple, que es útil para probar el tiempo de ejecución O (n) de un FMM. Más allá de esta lógica teórica, ¿hay beneficios al usar un Octree sobre otras estructuras de datos de árbol o trie?
Determinar la lista de interacción podría ser más fácil con un octree porque una celda conocería a sus vecinos inmediatos. Sin embargo, la lista de interacción es innecesaria si se usa un recorrido de árbol más dinámico como el recorrido de árbol dual .
Una alternativa sería un árbol kd. Una posible desventaja teórica es que la construcción requiere costosas operaciones de búsqueda mediana. Sin embargo, hay versiones de kd-trees que no requieren hallazgos medianos durante la construcción, aunque con particiones de espacio menos eficientes. En cuanto a la implementación, un árbol kd es muy simple.
Una alternativa más radical podría ser un árbol R .
Entonces, mi pregunta es: ¿qué pasa con los octrees que los convierten en la mejor opción para un FMM?
fuente
Respuestas:
Los comentarios anteriores dan algunas razones muy buenas para usar octrees (es decir, reducir a la mitad recursivamente el cubo computacional en cada dimensión en lugar de una bisección ortogonal más general). La simetría y la simplicidad de calcular listas de interacción es una gran ventaja.
Yo diría que quizás la característica más importante que los octrees traen a la mesa es que el teorema de adición que suscribe el FMM se cumple sistemáticamente para las interacciones de zonas lejanas independientes de la geometría con el criterio de separación muy simple de uno o más "amortiguadores" cajas En otras palabras, se garantiza que la representación de suma FMM del campo potencial converge con un orden creciente en circunstancias no patológicas.
fuente