Editing Quadtree (section)

===Compressed quadtrees===
This section summarizes a subsection from a book by [[Sariel Har-Peled]].<ref>{{Cite book|title=Geometric approximation algorithms|last=Har-Peled|first=S.|author-link=Sariel Har-Peled|publisher=Mathematical Surveys and Monographs Vol. 173, American mathematical society|year=2011|chapter=Quadtrees - Hierarchical Grids}}</ref>

If we were to store every node corresponding to a subdivided cell, we may end up storing a lot of empty nodes. We can cut down on the size of such sparse trees by only storing subtrees whose leaves have interesting data (i.e. "important subtrees"). We can actually cut down on the size even further. When we only keep important subtrees, the pruning process may leave long paths in the tree where the intermediate nodes have degree two (a link to one parent and one child). It turns out that we only need to store the node <math>u</math> at the beginning of this path (and associate some meta-data with it to represent the removed nodes) and attach the subtree rooted at its end to <math>u</math>. It is still possible for these compressed trees to have a linear height when given "bad" input points.

Although we trim a lot of the tree when we perform this compression, it is still possible to achieve logarithmic-time search, insertion, and deletion by taking advantage of [[Z-order curve|''Z''-order curves]]. The ''Z''-order curve maps each cell of the full quadtree (and hence even the compressed quadtree) in <math>O(1)</math> time to a one-dimensional line (and maps it back in <math>O(1)</math> time too), creating a total order on the elements. Therefore, we can store the quadtree in a data structure for ordered sets (in which we store the nodes of the tree). 

We must state a reasonable assumption before we continue: we assume that given two real numbers <math>\alpha, \beta \in [0, 1)</math> expressed as binary, we can compute in <math>O(1)</math> time the index of the first bit in which they differ. We also assume that we can  compute in <math>O(1)</math> time the lowest common ancestor of two points/cells in the quadtree and establish their relative ''Z''-ordering, and we can compute the floor function in <math>O(1)</math> time. 

With  these assumptions, point location of a given point <math>q</math> (i.e. determining the cell that would contain <math>q</math>), insertion, and deletion operations can all be performed in <math>O(\log{n})</math> time (i.e. the  time it takes to do a search in the underlying ordered set data structure).

To perform a point location for <math>q</math> (i.e. find its cell in the compressed tree):
# Find the existing cell in the compressed tree that comes before <math>q</math> in the ''Z''-order. Call this cell <math>v</math>.
# If <math>q \in v</math>, return <math>v</math>.
# Else, find what would have been the lowest common ancestor of the point <math>q</math> and the cell <math>v</math> in an uncompressed quadtree. Call this ancestor cell <math>u</math>.
# Find the existing cell in the compressed tree that comes before <math>u</math> in the ''Z''-order and return it.
Without going into specific details, to perform insertions and deletions we first do a point location for the thing we want to insert/delete, and then insert/delete it. Care must be taken to reshape the tree as appropriate, creating and removing nodes as needed.