ABSTRACT
In this chapter, the authors introduce the quadtree and octree structures. They present definition and complexity, the recursive construction scheme, and a standard application. Quadtrees can store many kinds of data. The authors describe the variant that stores a set of points and suggest a recursive definition. The general idea is to construct a quadtree over the grid, and then traverse this quadtree top-down in order to render it. The quadtree construction can be easily extended to octrees in 3D. The internal nodes of octrees have eight children, and the children correspond to boxes instead of squares. A canonical way to improve any grid-based method is to construct an octree. The octree leaves store lists of objects. The idea is to construct a complete octree over the cells of the grid. The leaves point to the lower-left node of their associated cell.
