K-D Tree Demo

A binary search tree for storing point data where the underlying space is decomposed into just two halves as the points are inserted. The partition positions depend on the data. The partition axes are cycled in the order x , y , x , y , ... For more details, see pages 50-57 and 761-763 of Samet, Foundations of Multidimensional and Metric Data Structures or, see pages 66-80 of Samet, Design and Analysis of Spatial Data Structures.