Quadtree
A quadtree is a tree data structure in which each internal node has exactly four children.
Formalization
We have points in the plane. We need a bounding box , i.e. a square containing all points.
- Find the smallest such that the max and values in are .
- Variation: Pick left coordinate based on min value, such that size is a power of 2
Structure (and also how to build the quadtree that stores ):
- Root of the quadtree is associated with region
- If contains 0 or 1 points, then root is a leaf that stores point
- Else split: Partition into four equal subsquares (quadrants) , , ,
- Partition into sets , , , of points in these regions
- Recursively build tree for points in region and make them children of the root
What if the point is on the line split?
The convention is that points on split lines belong to right/top side
Insert example