Efficient radius neighbor search in three-dimensional point clouds

Abstract

Finding all neighbors of a point inside a given radius is an integral part in many approaches using three-dimensional laser range data. We present novel insights to significantly improve the runtime performance of radius neighbor search using octrees. Our contributions are as follows: (1) We propose an index-based organization of the point cloud such that we can efficiently store start and end indexes of points inside every octant and (2) exploiting this representation, we can use pruning of irrelevant subtrees in the traversal to facilitate highly efficient radius neighbor search. We show significant runtime improvements of our proposed octree representation over state-of-the-art neighbor search implementations on three different urban datasets.