Tree data structure in which each internal node has exactly four children, to partition a 2D area
This article has an unclear citation style. The references used may be made clearer with a different or consistent style of citation and footnoting.(April 2015) (Learn how and when to remove this message)
Quadtree
Type
Tree
Invented
1974
Invented by
Raphael Finkel and J.L. Bentley
Time complexity in big O notation
Operation
Average
Worst case
Space complexity
A point-region quadtree with point data. Bucket capacity 1.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. This data structure was named a quadtree by Raphael Finkel and J.L. Bentley in 1974.[1] 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 (T-pyramid) is a "complete" tree; every node of the T-pyramid has four child nodes except leaf nodes; all leaves are on the same level, the level that corresponds to individual pixels in the image. The data in a tree-pyramid can be stored compactly in an array as an implicit data structure similar to the way a complete binary tree can be stored compactly in an array.[2]
^Finkel, R. A.; Bentley, J. L. (1974). "Quad trees a data structure for retrieval on composite keys". Acta Informatica. 4 (1): 1–9. doi:10.1007/BF00288933. S2CID 33019699. Retrieved 6 November 2019.
^
Milan Sonka, Vaclav Hlavac, Roger Boyle.
"Image Processing, Analysis, and Machine Vision".
2014.
p. 108-109.
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...
infinite grid, with the pattern in question centered near the origin. A quadtree (with sharing of nodes) is used to represent the field. A node at the kth...
subdividing it into eight octants. Octrees are the three-dimensional analog of quadtrees. The word is derived from oct (Greek root meaning "eight") + tree. Octrees...
complex objects as compared using an arbitrary metric. Octree PH-tree Quadtree R-tree: Typically the preferred method for indexing spatial data. Objects...
Implicit k-d tree Min/max k-d tree Relaxed k-d tree Adaptive k-d tree Quadtree Octree Linear octree Z-order UB-tree R-tree R+ tree R* tree Hilbert R-tree...
constant k > 1. The algorithm uses shifted quadtrees. The key concept of the algorithm is alignment to the quadtree grid. An object of size r is called k-aligned...
generalization of other spatial tree structures such as k-d trees and quadtrees, one where hyperplanes that partition the space may have any orientation...
{content-type: text/plain OR x-gis/x-shapefile } .qix — an alternative quadtree spatial index used by MapServer and GDAL/OGR software {content-type: x-gis/x-shapefile}...
regular objects such as heightfields and polygon meshes tend to employ quadtrees and octrees, which are specialized variants of a 3D bounding box hierarchy...
are merged to create the segmented result. The technique incorporates a quadtree data structure, meaning that there is a parent-child node relationship...
paradigms. Finkel and J.L. Bentley created the data structure called the quadtree. Finkel was born in Chicago. He entered the University of Chicago, where...
approaches to terrain rendering. [1] Prior to geomipmapping, techniques such as quadtree rendering were used to divide the terrain into square tiles created by...
called superblocks of 64×64 pixels which are adaptively subpartitioned in a quadtree coding structure. They can be subdivided either horizontally or vertically...
the Böröczky tiling) is a tiling of the hyperbolic plane, resembling a quadtree over the Poincaré half-plane model of the hyperbolic plane. It was first...
Kirchhoffer; Haricharan Lakshman; et al. "Video Compression Using Nested Quadtree Structures, Leaf Merging and Improved Techniques for Motion Representation...
Wróblewski, P.; Midura, M. (October 2021). "A Finite Volume Method using a Quadtree Non-Uniform Structured Mesh for Modeling in Electrical Capacitance Tomography"...
the cell ID. The ID is usually used as spatial index (such as internal Quadtree or k-d tree), but is also possible to transform ID into a human-readable...
accelerated by the use of new RT cores, which are designed to process quadtrees and spherical hierarchies, and speed up collision tests with individual...
compression efficiency, AVS2 adopts a block partition structure based on the quadtree, including the CU (Coding Unit), PU (Prediction Unit) and TU (Transform...
minimization, decision trees, grammatical inference, hierarchical clustering, and quadtree decomposition are all examples of function decomposition. Many statistical...
Global Information
