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.
