Range Search

kd-Tree

Soham was explaining this to me to improve the speedup of comparing speeds.

k-d tree is a space-partitioning data structure for organizing points in a k-dimensional space. It is a more generic implementation of a Binary Search Tree.

Soham was talking about thinking about splitting your trees into different Hyperplanes?

Resources

• https://www.youtube.com/watch?v=BK5x7IUTIyU&ab_channel=Computerphile
• https://pointclouds.org/documentation/group__kdtree.html

Wow, I am learning this in CS240.

Very similar to Quadtree…?

Formalization

We have $n$ points $S=\{(x_0,y_0),(x_1,y_1),\cdot \cdot \cdot ,(x_{n-1},y_{n-1})\}$.

Quadtrees split square into quadrants regardless of where points are.

(Point-based) kd-tree idea: Split the region such that (roughly) half the point are in each subtree.

• Each node of the kd-tree keeps track of a splitting line in one dimension (2D: either vertical or horizontal)
• Continue splitting, switching between vertical and horizontal lines, until every point is in a separate region

Convention

Similar to what we do with Quadtrees, the points on split lines belong to right/top side.