According to wikipedia a kd-tree (short for k-dimensional tree) is a space-partitioning data structure for organiizing points in a k-dimensional space. In this implementation, points are represented as a boost ublas matrix (numPoints x dimPoints) and the kd-tree can be seen as a row permutation of the matrix. The tree is built recursively. At depth k, the (k % dimPoints) coordinates are analyzed for all the points and the median of them is selected with a quickselect algorithm. The quickselection induces a natural row-index permutation for points in two sets, which are recursively partitioned on the next levels of the tree.
Here you have the code.
The Future Of Mobile-Social Could Spell The End For Social Networks - [image: GoogleIO]*Editor's note: * *Keith Teare is the founder of just.me and a partner at Archimedes Labs. He is also the co-founder of TechCrunch. *This w...
1 hour ago