in each node are arbitrary Related variations: Quadtree, a space-partitioning structure that splits in two dimensions simultaneously, so that each node has 4 children Octree, a space-partitioning structure that splits in three dimensions simultaneously, so that each node has 8 children Ball tree, a multi-dimensional space partitioning useful for nearest neighbor search R-tree and bounding interval hierarchy, structure for partitioning objects rather than points, with overlapping regions Vantage-point tree, a variant of a k-d tree that uses hyperspheres instead of hyperplanes to partition the data Problems that can be addressed with k-d trees: Recursive partitioning, a technique for constructing statistical decision trees that are similar to k-d trees Klee's measure problem, a problem of computing the area of a union of rectangles, solvable using k-d trees Guillotine problem, a problem of finding a k-d tree whose cells are large enough to contain a given set of rectangles Open source implementations ALGLIB has C# and C++ implementations of k-d tree based nearest neighbor and approximate nearest neighbor algorithms CGAL the Computational Algorihms Library, has an implementations of k-d tree based nearest neighbor, approximate nearest neighbor as well as range search algorithms. SciPy, a Python library for scientific computing, contains implementations of k-d tree based nearest neighbor lookup algorithms. scikit-learn, a Python library for machine learning, contains implementations of k-d trees to back nearest neighbor and radius neighbors searches. References Computer graphics data structures Trees (data structures) Geometric data structures Database index techniques Data types Articles with example Python (programming language) code