Mar 17, 2017
Day 76 - k-d Tree
Another spatial subdivision technique, the k-dimensional tree organizes points into a binary search tree where each point splits space along a hyperplane. In 2D, shown in the animation, a hyperlane is just a simple line, so a 2D k-d tree creates rectangular regions where each point splits space into a left and right region. Any children of that point will split space along the other axis. It’s grandchildren will split space along the same axis (in 2D, of course). This technique makes nearest neighbor lookups significantly faster.
