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

arXiv: https://arxiv.org/abs/2102.10808 · HTML: https://mlsanity.com/paper/2102.10808/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Feb 2021.

## Built on by (most cited first, 9 of 9)

- [ImMesh: An Immediate LiDAR Localization and Meshing Framework](https://mlsanity.com/paper/2301.05206/) (2023)
- [SED-MVS: Segmentation-Driven and Edge-Aligned Deformation Multi-View Stereo with Depth Restoration and Occlusion Constraint](https://mlsanity.com/paper/2503.13721/) (2025)
- [HiSC4D: Human-centered interaction and 4D Scene Capture in Large-scale Space Using Wearable IMUs and LiDAR](https://mlsanity.com/paper/2409.04398/) (2024)
- [Real-Time Simultaneous Localization and Mapping with LiDAR intensity](https://mlsanity.com/paper/2301.09257/) (2023)
- [Generalized-CVO: Fast and Correspondence-Free Local Point Cloud Registration with Second Order Riemannian Optimization](https://mlsanity.com/paper/2606.10019/) (2026)
- [Robust Second-order LiDAR Bundle Adjustment Algorithm Using Mean Squared Group Metric](https://mlsanity.com/paper/2409.01856/) (2024)
- [EROAM: Event-based Camera Rotational Odometry and Mapping in Real-time](https://mlsanity.com/paper/2411.11004/) (2024)
- [Self-Balancing, Memory Efficient, Dynamic Metric Space Data Maintenance, for Rapid Multi-Kernel Estimation](https://mlsanity.com/paper/2504.18003/) (2025)
- [GARLIC: GAussian Representation LearnIng for spaCe partitioning](https://mlsanity.com/paper/2505.24608/) (2025)

## Abstract (arXiv)

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.