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. Commented Jul 3, 2014 at 18:11
• Determining interaction lists should be quite easy with any form of hierarchical space decomposition. Commented Jul 7, 2014 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. Commented Jul 8, 2014 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. Commented Apr 17, 2016 at 22:39
• Octrees are a natural outcome of domain decomposition in three dimensions. Commented Apr 29, 2016 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.