Pourquoi Octrees est-il utilisé pour la décomposition d'espace multipolaire?

18

Dans la plupart (toutes?) Des implémentations de la méthode multipolaire rapide (FMM), les octrees sont utilisés pour décomposer le domaine concerné. Théoriquement, les octrees fournissent une borne volumétrique simple, qui est utile pour prouver le temps d'exécution O (n) d'un FMM. Au-delà de cette justification théorique, y a-t-il des avantages à utiliser un octree par rapport à d'autres structures de données d'arbre ou de trie?

La détermination de la liste d'interaction pourrait être plus facile avec un octree car une cellule connaîtrait ses voisins immédiats. Cependant, la liste d'interaction n'est pas nécessaire en utilisant une traversée d'arbre plus dynamique comme la double traversée d' arbre .

Une alternative serait un arbre kd. Un inconvénient théorique possible est que la construction nécessite des opérations de recherche médianes coûteuses. Cependant, il existe des versions de kd-trees qui ne nécessitent pas de recherche médiane pendant la construction, mais avec un partitionnement d'espace moins efficace. Côté implémentation, un arbre kd est très simple.

Une alternative plus radicale pourrait être un R-tree .

Donc, ma question est la suivante: qu'en est-il d'Octrees qui en font le meilleur choix pour un FMM?

algorithms Ben Thompson
la source
4
Je pense que cela rend la détermination des listes d'interaction (quels observateurs sont dans le champ lointain de quelles sources) particulièrement facile.
rchilton1980
La détermination des listes d'interactions devrait être assez facile avec toute forme de décomposition d'espace hiérarchique.
Ben Thompson
1
Je suis d'accord avec vous sur le fait que les oct-arbres sont théoriquement simples à analyser. D'autres algorithmes de sommation rapide, tels que les (qui sont des généralisations algébriques de FMM) utilisent différents arbres, tels que la bissection géométrique ou le fractionnement basé sur un cluster. H
user2457602
1
Je ne suis pas un expert en la matière, mais peut-être que le fait que les octrees aient plus de «symétrie» joue un rôle? Les partitions dans un octree sont disposées régulièrement et ont la même forme carrée, ce qui pourrait aider à réaliser les extensions multipolaires par rapport, par exemple, à un arbre kd.
Jannis Teunissen
Les octrees sont un résultat naturel de la décomposition du domaine en trois dimensions.
gpavanb

Réponses:

3

Les commentaires ci-dessus donnent de très bonnes raisons d'utiliser des octrois (c'est-à-dire de réduire récursivement de moitié le cube de calcul dans chaque dimension par opposition à une bissection orthogonale plus générale). La symétrie et la simplicité de calcul des listes d'interactions sont un gros plus.

Je dirais que peut-être la caractéristique la plus importante que les octrois apportent à la table est que le théorème d'addition souscrivant le FMM est systématiquement satisfait pour les interactions de zone éloignée indépendantes de la géométrie avec le critère de séparation très simple d'un ou plusieurs "tampon" des boites. En d'autres termes, la représentation de somme FMM du champ potentiel est garantie de converger avec un ordre croissant dans des circonstances non pathologiques.

smh
la source