Name of the generalization of quadtree and octree?

What is the name of the equivalent of quadtrees and octrees in n-dimension ?


Since the generalization of quadrants and octants is the orthant, I'd have thought "orthtree" would make sense. But I only turned up one or two papers using this term. The term "hyperoctree" seems to be far more common in the literature.


Note that quadtree/octree-type structures tend not to be used as one goes up much further in dimension because of the classic 'combinatorial explosion' of the splitting factor; a node that needs to be split will yield $2^d$ children even if many of them are empty. Instead, once the dimension goes up (and often even in two and three dimensions) the more common structure is a binary tree where each internal node corresponds to an axis-orthogonal split (though these splits typically don't have to partition their volume evenly). These are known as k-d trees; you should be able to find quite a bit of information about them out there.


Strictly speaking, k-d trees are not a generalization of quadtrees/octrees, but it may be what you are looking for: http://en.wikipedia.org/wiki/K-d_tree