Quadtree

Source: Geometric Approximation Algorithms

A quadtree is a decomposition of some bounded region of into hypercubes.

Construction

Let , and let the root node correspond to the hypercube . The children of this node are defined to be partitioning hypercubes with half edge length. To actually construct the tree, start with the root node, and continuously expand into child nodes until the leaf nodes are empty or only contain point.

Path Compression

If two points are very close to each other, the naive construction can have arbitrarily long empty paths. This can be alleviated by “compressing” these empty levels into a single node. It is possible to compute this in time