Na maioria das (todas?) Implementações do Fast Multipole Method (FMM), os octrees são usados para decompor o domínio relevante. Teoricamente, os octrees fornecem um limite volumétrico simples, útil para provar o tempo de execução O (n) de um FMM. Além dessa lógica teórica, há benefícios em usar um Octree sobre outras estruturas de árvore ou dados?
Determinar a lista de interação pode ser mais fácil com uma octree, porque uma célula conhecerá seus vizinhos imediatos. No entanto, a lista de interação é desnecessária usando um percurso de árvore mais dinâmico como o Dual Tree Traversal .
Uma alternativa seria uma árvore kd. Uma possível desvantagem teórica é que a construção requer operações medianas caras de busca. No entanto, existem versões do kd-trees que não exigem descoberta mediana durante a construção - embora com particionamento de espaço menos eficiente. Em termos de implementação, uma árvore kd é muito simples.
Uma alternativa ainda mais radical pode ser uma árvore-R .
Então, minha pergunta é: o que acontece com o Octrees que os torna a melhor escolha para um FMM?
fonte
Respostas:
Os comentários acima fornecem algumas boas razões para usar octrees (ou seja, reduzir recursivamente pela metade o cubo computacional em cada dimensão, em oposição a uma bissecção ortogonal mais geral). Simetria e simplicidade no cálculo de listas de interação são uma grande vantagem.
Eu argumentaria que talvez a característica mais importante que os octrees trazem para a tabela seja que o teorema da adição que subscreve o FMM é sistematicamente satisfeito para interações de zonas distantes, independentemente da geometria, com o critério extremamente simples de separação de um ou mais "buffer" caixas. Em outras palavras, a representação da soma FMM do campo potencial é garantida para convergir com o aumento da ordem em circunstâncias não patológicas.
fonte