Quadtree

Uncommon card · No. 194243

A quadtree is a tree data structure in which each internal node has exactly four children. Quadtrees are the two-dimensional analog of octrees and are most often used to partition a two-dimensional space by recursively subdividing it into four quadrants or regions. The data associated with a leaf cell varies by application, but the leaf cell represents a "unit of interesting spatial information". The subdivided regions may be square or rectangular, or may have arbitrary shapes. Although similar subdivisions were used much earlier (for instance in the Whitney covering lemma of 1934), this data structure was named a quadtree by Raphael Finkel and J.L. Bentley in 1974. A similar partitioning is also known as a Q-tree. All forms of quadtrees share some common features: They decompose space into adaptable cells. Each cell (or bucket) has a maximum capacity. When maximum capacity is reached, the bucket splits. The tree directory follows the spatial decomposition of the quadtree. A tree-pyramid...

Read on Wikipedia · Image David Eppstein, Public domain