Introduction

A tree data structure that recursively divides a 2-D region into quadrants is called a quadtree. (http://en.wikipedia.org/wiki/Quadtree) The 3-D equivalent is an octree. The N-D analogue of the 2-D quadrant and the 3-D octant is an orthant. (http://en.wikipedia.org/wiki/Orthant) In N-D space there are orthants. A tree that recursively divides space into orthants has been called an N-D quadtree and a hyper-octree. We think the term orthtree is a descriptive and succinct name for such data structures. As we have implemented a data structure that is generic in the space dimension (the dimension is a template parameter) we will use the term orthtree instead of quadtree or octree.

There are two primary methods of representing an orthtree: pointer-based and linear. With a pointer-based representation, one stores the branches as well as the leaves of the tree. Each branch stores pointers to nodes in the tree. Here we use the term node to refer to either a branch or a leaf. These pointers the to children of each branch are necessary for searching for a leaf. Usually, each node also stores a pointer to its parent. This is convenient for many algorithms, including traversing the nodes. The position of a leaf is implicitly stored in the branches leading from the root to the leaf.

With the linear representation of an orthtree, only the leaves are stored. Instead of implicitly representing the positions of the leaves with branches, spatial indices are used to explicitly describe these positions. In this context, we call the pair of a spatial index and the leaf a node. "Linear" refers to the fact that the nodes may be stored in a sequence container (an array, for example). A specific node may be accessed by searching for its spatial index.