  This paper proposes 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.
Besides point-wise operations, the ikd-Tree supports several features such as
box-wise operations and down-sampling that are practically useful in robotic
applications. In parallel to the incremental operations (i.e., insert,
re-insert, and delete), ikd-Tree actively monitors the tree structure and
partially re-balances the tree, which enables efficient nearest point search in
later stages. The ikd-Tree is carefully engineered and supports multi-thread
parallel computing to maximize the overall efficiency. We validate the ikd-Tree
in both theory and practical experiments. On theory level, a complete time
complexity analysis is presented to prove the high efficiency. On experiment
level, the ikd-Tree is tested on both randomized datasets and real-world LiDAR
point data in LiDAR-inertial odometry and mapping application. In all tests,
ikd-Tree consumes only 4% of the running time in a static k-d tree.
