quadtree

thumb|300px|A point-region quadtree with point data. Bucket capacity 1. thumb|300x300px|Quadtree compression of an image step by step. Left shows the compressed image with the tree bounding boxes while the right shows just the compressed image 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.