# RadiusFPS: Efficient Farthest Point Sampling on CPUs and GPUs via Spherical Voxel Pruning

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 25 of its 40 references that are in the map.
- First posted on arXiv 4 Jun 2026.

## Builds on (most cited first, 25 of 25)

- [PointNet++: Deep Hierarchical Feature Learning on Point Sets in a Metric Space](https://mlsanity.com/paper/1706.02413/) (2017)
- [ScanNet: Richly-annotated 3D Reconstructions of Indoor Scenes](https://mlsanity.com/paper/1702.04405/) (2017)
- [4D Spatio-Temporal ConvNets: Minkowski Convolutional Neural Networks](https://mlsanity.com/paper/1904.08755/) (2019)
- [KPConv: Flexible and Deformable Convolution for Point Clouds](https://mlsanity.com/paper/1904.08889/) (2019)
- [PointRCNN: 3D Object Proposal Generation and Detection from Point Cloud](https://mlsanity.com/paper/1812.04244/) (2018)
- [Point-BERT: Pre-training 3D Point Cloud Transformers with Masked Point Modeling](https://mlsanity.com/paper/2111.14819/) (2021)
- [Frustum PointNets for 3D Object Detection from RGB-D Data](https://mlsanity.com/paper/1711.08488/) (2017)
- [Point Transformer V3: Simpler, Faster, Stronger](https://mlsanity.com/paper/2312.10035/) (2023)
- [RandLA-Net: Efficient Semantic Segmentation of Large-Scale Point Clouds](https://mlsanity.com/paper/1911.11236/) (2019)
- [Masked Autoencoders for Point Cloud Self-supervised Learning](https://mlsanity.com/paper/2203.06604/) (2022)
- [3DSSD: Point-based 3D Single Stage Object Detector](https://mlsanity.com/paper/2002.10187/) (2020)
- [PointNeXt: Revisiting PointNet++ with Improved Training and Scaling Strategies](https://mlsanity.com/paper/2206.04670/) (2022)
- [Point Transformer V2: Grouped Vector Attention and Partition-based Pooling](https://mlsanity.com/paper/2210.05666/) (2022)
- [STD: Sparse-to-Dense 3D Object Detector for Point Cloud](https://mlsanity.com/paper/1907.10471/) (2019)
- [Not All Points Are Equal: Learning Highly Efficient Point-based Detectors for 3D LiDAR Point Clouds](https://mlsanity.com/paper/2203.11139/) (2022)
- [Grid-GCN for Fast and Scalable Point Cloud Learning](https://mlsanity.com/paper/1912.02984/) (2019)
- [Towards Large-scale 3D Representation Learning with Multi-dataset Point Prompt Training](https://mlsanity.com/paper/2308.09718/) (2023)
- [Semantic Segmentation for Real Point Cloud Scenes via Bilateral Augmentation and Adaptive Fusion](https://mlsanity.com/paper/2103.07074/) (2021)
- [Meta Architecture for Point Cloud Analysis](https://mlsanity.com/paper/2211.14462/) (2022)
- [3DCTN: 3D Convolution-Transformer Network for Point Cloud Classification](https://mlsanity.com/paper/2203.00828/) (2022)
- [PointAcc: Efficient Point Cloud Accelerator](https://mlsanity.com/paper/2110.07600/) (2021)
- [PointVector: A Vector Representation In Point Cloud Analysis](https://mlsanity.com/paper/2205.10528/) (2022)
- [An Adjustable Farthest Point Sampling Method for Approximately-sorted Point Cloud Data](https://mlsanity.com/paper/2208.08795/) (2022)
- [Point-GN: A Non-Parametric Network Using Gaussian Positional Encoding for Point Cloud Classification](https://mlsanity.com/paper/2412.03056/) (2024)
- [FastPoint: Accelerating 3D Point Cloud Model Inference via Sample Point Distance Prediction](https://mlsanity.com/paper/2507.23480/) (2025)

## Abstract (arXiv)

Point clouds are a primary sensory representation for robotic perception, underpinning LiDAR-based autonomous driving, simultaneous localization and mapping (SLAM), and navigation. Within these pipelines, Farthest Point Sampling (FPS) is the most well-known downsampling operator, as its uniform coverage preserves the geometric structure on which downstream perception relies. However, the large time complexity of classical FPS scales poorly with the million-point-per-second rates of modern 3D sensors, making it a dominant latency bottleneck that conflicts with the real-time and limited onboard compute budgets of robotic systems. Therefore, we propose RadiusFPS, an FPS acceleration framework based on spherical voxel pruning that preserves the standard FPS update rule under the same initialization and tie-breaking policy. By indexing the point cloud with spherical voxels, RadiusFPS derives a conservative geometric bound that prunes redundant distance computations in each iteration, complemented by a coordinate-wise point-skip test that removes residual updates. We further introduce RadiusFPS-G, a warp-level GPU implementation that fuses voxel selection, pruning, and distance update into memory-coalesced kernels, eliminating costly global-memory round-trips. On indoor (S3DIS, ScanNet) and outdoor LiDAR (SemanticKITTI) benchmarks, RadiusFPS-G attains up to 2.5x speedup over GPU-based FPS and matches or exceeds QuickFPS among the evaluated methods while using roughly half its GPU memory, with comparable segmentation accuracy. When coupled with the learning-based FastPoint sampler, the resulting pipeline achieves the fastest End-to-End inference among all evaluated configurations. These properties make high-quality FPS-style sampling practical for latency- and memory-constrained robotic vision.