NS-FPS: Accelerating Farthest Point Sampling via Neighbor Search in Large-Scale Point Clouds

With the rapid advancement of LiDAR sensors, processing large-scale point clouds has become a significant challenge in applications such as autonomous driving. One critical operation in point cloud processing is Farthest Point Sampling (FPS), which is essential for preserving geometric features in neural networks. However, the computational complexity of FPS grows quadratically with point cloud size, resulting in substantial memory access overhead and high latency. In this paper, we propose NS-FPS, a hardware-software codesigned accelerator that transforms the FPS problem into a neighbor search problem, reducing the complexity from $\mathcal{O}\left(N^{2}\right)$ to $\mathcal{O}(N \log N)$. We observe that distance-cache updates during sampling occur primarily around the current sampled region, implying that most point accesses and distance computations are redundant. Using Voronoi diagram (VD) geometry, we explain this phenomenon and reveal a strong connection between FPS behavior and local neighborhood structure. Leveraging this insight, we introduce a partial-update strategy. We organize point cloud data using Morton codes, developing a three-level memory scheme that exploits spatial locality. Combined with an efficient pipelined neighbor search scheme and a hierarchical maximum candidate search, NS-FPS minimizes memory accesses and computational overhead, fully exploiting the acceleration potential of the reformulated algorithm. We implement NS-FPS as both a CPU software version and a custom ASIC design. Evaluated on real-world point cloud datasets, NS-FPS achieves an $\mathbf{8 1. 6} \times$ speedup and $\mathbf{1 7 0 0} \times$ reduction in memory accesses compared to GPU-based implementations, and a $2.9 \times$ speedup with 13.4× reduction in memory accesses compared to existing point cloud sampling accelerators. These results highlight that NS-FPS is an efficient and scalable solution for real-time point cloud processing in large-scale applications. The code is available at https://github.com/satreeby/ns-fps/.