top of page


ikd-Tree: An Incremental K-D Tree for Robotic Applications


Mr. Yixi CAI

PhD candidate in the Mechanical Engineering Dept.

Date & Time

Thursday, 22 April 2021

3:00 am


Via Zoom


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.

Research Areas:

Robotics and Control

Contact for


Dr. F. Zhang

+(852) 3917 7909

Download Details

in PDF

bottom of page