# 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}),⋅⋅⋅,(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.