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?