Cheesemap: A high-performance point-indexing data structure for neighbor search in LiDAR data

Abstract

Point-cloud data, as the representation of three-dimensional spatial information, is a fundamental piece of information in various domains where indexing and querying these point clouds efficiently is crucial for tasks such as object recognition, autonomous navigation, and environmental modeling. In this paper, we present a novel data structure, cheesemap, designed for fast neighbor search in 3D LiDAR point clouds. Points are indexed using a grid of voxels, which can be organized in three different ways, originating three flavors of the cheesemap: dense, sparse, and mixed. The lookup of the voxels is theoretically ensured to be performed in constant or amortized constant time, speeding up the search for neighboring points. Experimental results show that cheesemap can outperform, in terms of performance and memory footprint, other state-of-the-art data structures both in region-based and k-NN queries throughout different types of point clouds, particularly for Airborne Laser Scanning (ALS) point clouds