MX Quadtree Demo
Point data is treated as if it is nonzero data in a matrix. The finest
level of decomposition is known in advance. The underlying space is recursively
decomposed into four equal area blocks until obtaining a 1 by 1 cell corresponding
to the data point. Empty cells are merged into larger cells. Four occupied
cells are not merged. The partition positions are independent of the data.
For more
details, see pages 38-42 and 756-758 of Samet,
Foundations of Multidimensional and Metric Data Structures
or, see pages 86-92 of Samet,
Design and Analysis of Spatial Data
Structures.