k-Dimensional Trees

Computational geometry is generally concerned with algorithms that solve problems that can be stated in purely geometric terms like: find the smallest polygon which encloses a set of points or construct a data structure to support efficient querying of a set of points. I once interviewed at company that relied on methods from this field. It was during an afternoon one-on-one interview that the k-d tree data structure came up. We, the interviewer and I, were discussing how to find the closest point in a point cloud. At the time, I struggled to find the answer (we were in bonus territory, anyway:)). He explained how one could create a data structure that partitioned the point space into finer and finer cells. And if one keeps track of the relationship between a cell and its constituents, then one can quickly search the space. Essentially, that is what a k-d tree does for point clouds.

k-D dimensional trees are data structures that allow for fast search and querying of point sets. These binary trees have nodes which are k-dimensional points. The tree organizes points by partitioning the point space along each coordinate axis.

... read more