[prev] 18 [next]

Quad Trees

Quad trees use regular, disjoint partitioning of tuple space.
  • for 2d, partition space into quadrants (NW, NE, SW, SE)
  • each quadrant can be further subdivided into four, etc.
Example:

[Diagram:Pics/select/quad-tree-space.png]