Abstract:

The K-Dimensional Tree (K-D Tree) is an efficient data structure that organizes multi-dimensional point data which enables fast search of nearest neighbors, an essential operation that is widely required in various robotic applications. For example, in LiDAR odometry and mapping, k-d tree-based nearest point search is crucial to match a point in a new LiDAR scan to its correspondences in the map (or the previous scan). Nearest point search is also important in motion planning for fast obstacle collision check on point-cloud.This seminar will introduce an efficient data structure, ikd-Tree, for dynamic space partition. The ikd-Tree incrementally updates a k-d tree with new coming points only, leading to much lower computation time than existing static k-d trees. The design and implementation of incremental updates and nearest search on ikd-Tree will be introduced in detail together with validation on both theory and practice level.