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.