Uses of Quadtrees
- Spatial indexing: O(log n) lookup of data values by spatial
position, while using less storage than an array.
- Numerical algorithms: spatial algorithms can be much more efficient
by using lower-resolution data for interactions that are far apart.
- Graphics: reduce resolution except where user is looking.
An octtree is a 3-dimensional tree similar to a quadree.