Why are Octrees used for Multipole space decomposition?

Question

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?

Answer 1

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.