PR k-d Tree Demo

Recursively decompose the underlying space into two equal area blocks until each block contains at most one data point. The partition axes are cycled in the order x , y , x , y , ... The partition positions are independent of the data. For more details, see pages 71-72 of Samet, Foundations of Multidimensional and Metric Data Structures or, see pages 93-94 of Samet, Design and Analysis of Spatial Data Structures.