# Why are Octrees used for Multipole space decomposition?

In most (all?) implementations of the Fast Multipole Method (FMM), octrees are used to decompose the relevant domain. Theoretically, octrees provide a simple volumetric bound, which is useful for proving the O(n) runtime of a FMM. Beyond this theoretical rationale, are there benefits to using an Octree over other tree or trie data structures?

Determining the interaction list might be easier with an octree because a cell would know its immediate neighbors. However, the interaction list is unnecessary using a more dynamic tree traversal like Dual Tree Traversal.

An alternative would be a kd-tree. One possible theoretical downside is that construction requires expensive median finding operations. However, there are versions of kd-trees that do not require median finding during construction -- albeit with less efficient space partitioning. Implemention-wise, a kd-tree is very simple.

An even more radical alternative might be an R-tree.

So, my question is: What is about Octrees that make them the best choice for a FMM?

• I think it makes determining the interaction lists (which observers are in the far field of which sources) particularly easy. – rchilton1980 Jul 3 '14 at 18:11
• Determining interaction lists should be quite easy with any form of hierarchical space decomposition. – Ben Thompson Jul 7 '14 at 12:36
• I agree with you in that, oct-trees are theoretically simple to analyze. Other fast summation algorithms, such as $\mathcal{H}$-matrices (which are algebraic generalizations of FMM) use different trees, such as geometric bisection or cluster based splitting. – user2457602 Jul 8 '14 at 0:28
• I'm no expert on this, but perhaps the fact that octrees have more 'symmetry' plays a role? The partitions in an octree are arranged regularly and have the same square shape, which could help in making the multipole expansions compared to e.g. a k-d tree. – Jannis Teunissen Apr 17 '16 at 22:39
• Octrees are a natural outcome of domain decomposition in three dimensions. – gpavanb Apr 29 '16 at 5:53

## 1 Answer

The comments above give some very good reasons for using octrees (i.e., recursively halving the computational cube in each dimension as opposed to a more general orthogonal bisection). Symmetry and simplicity of calculating interaction lists is a big plus.

I would argue that perhaps the most important feature that octrees bring to the table is that the addition theorem underwriting the FMM is systematically satisfied for far-zone interactions independent of the geometry with the extremely simple well-separatedness criterion of one or more "buffer" boxes. In other words, the FMM sum representation of the potential field is guaranteed to converge with increasing order under non-pathological circumstances.