# An Adjustable Farthest Point Sampling Method for Approximately-sorted Point Cloud Data

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 21 references that are in the map.
- First posted on arXiv 18 Aug 2022.

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

- [PointNet: Deep Learning on Point Sets for 3D Classification and Segmentation](https://mlsanity.com/paper/1612.00593/) (2016)
- [PointNet++: Deep Hierarchical Feature Learning on Point Sets in a Metric Space](https://mlsanity.com/paper/1706.02413/) (2017)
- [ShapeNet: An Information-Rich 3D Model Repository](https://mlsanity.com/paper/1512.03012/) (2015)
- [PointRCNN: 3D Object Proposal Generation and Detection from Point Cloud](https://mlsanity.com/paper/1812.04244/) (2018)
- [PCT: Point cloud transformer](https://mlsanity.com/paper/2012.09688/) (2020)
- [RandLA-Net: Efficient Semantic Segmentation of Large-Scale Point Clouds](https://mlsanity.com/paper/1911.11236/) (2019)
- [PointASNL: Robust Point Clouds Processing using Nonlocal Neural Networks with Adaptive Sampling](https://mlsanity.com/paper/2003.00492/) (2020)
- [Grid-GCN for Fast and Scalable Point Cloud Learning](https://mlsanity.com/paper/1912.02984/) (2019)
- [SampleNet: Differentiable Point Cloud Sampling](https://mlsanity.com/paper/1912.03663/) (2019)
- [Streaming Object Detection for 3-D Point Clouds](https://mlsanity.com/paper/2005.01864/) (2020)

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

- [How Many Tokens Do 3D Point Cloud Transformer Architectures Really Need?](https://mlsanity.com/paper/2511.05449/) (2025)
- [Nexels: Neurally-Textured Surfels for Real-Time Novel View Synthesis with Sparse Geometries](https://mlsanity.com/paper/2512.13796/) (2025)
- [HccePose(BF): Predicting Front & Back Surfaces to Construct Ultra-Dense 2D-3D Correspondences for Pose Estimation](https://mlsanity.com/paper/2510.10177/) (2025)
- [ArrowPose: Segmentation, Detection, and 5 DoF Pose Estimation Network for Colorless Point Clouds](https://mlsanity.com/paper/2506.08699/) (2025)
- [Hierarchical Adaptive Voxel-guided Sampling for Real-time Applications in Large-scale Point Clouds](https://mlsanity.com/paper/2305.14306/) (2023)
- [TS40K: a 3D Point Cloud Dataset of Rural Terrain and Electrical Transmission System](https://mlsanity.com/paper/2405.13989/) (2024)
- [VoLUT: Efficient Volumetric streaming enhanced by LUT-based super-resolution](https://mlsanity.com/paper/2502.12151/) (2025)
- [FastPoint: Accelerating 3D Point Cloud Model Inference via Sample Point Distance Prediction](https://mlsanity.com/paper/2507.23480/) (2025)
- [Stealthy and Robust Backdoor Attack against 3D Point Clouds through Additional Point Features](https://mlsanity.com/paper/2412.07511/) (2024)
- [Detecting Dental Landmarks from Intraoral 3D Scans: the 3DTeethLand challenge](https://mlsanity.com/paper/2512.08323/) (2025)
- [Symmetry Matters: Auditing and Symmetrizing 3D Generative Models](https://mlsanity.com/paper/2512.18953/) (2025)
- [Fast Attention-Based Simplification of LiDAR Point Clouds for Object Detection and Classification](https://mlsanity.com/paper/2603.07593/) (2026)
- [An End-to-End Framework for Functionality-Embedded Provenance Graph Construction and Threat Interpretation](https://mlsanity.com/paper/2603.17100/) (2026)
- [RadiusFPS: Efficient Farthest Point Sampling on CPUs and GPUs via Spherical Voxel Pruning](https://mlsanity.com/paper/2606.06255/) (2026)

## Abstract (arXiv)

Sampling is an essential part of raw point cloud data processing such as in the popular PointNet++ scheme. Farthest Point Sampling (FPS), which iteratively samples the farthest point and performs distance updating, is one of the most popular sampling schemes. Unfortunately it suffers from low efficiency and can become the bottleneck of point cloud applications. We propose adjustable FPS (AFPS), parameterized by M, to aggressively reduce the complexity of FPS without compromising on the sampling performance. Specifically, it divides the original point cloud into M small point clouds and samples M points simultaneously. It exploits the dimensional locality of an approximately sorted point cloud data to minimize its performance degradation. AFPS method can achieve 22 to 30x speedup over original FPS. Furthermore, we propose the nearest-point-distance-updating (NPDU) method to limit the number of distance updates to a constant number. The combined NPDU on AFPS method can achieve a 34-280x speedup on a point cloud with 2K-32K points with algorithmic performance that is comparable to the original FPS. For instance, for the ShapeNet part segmentation task, it achieves 0.8490 instance average mIoU (mean Intersection of Union), which is only 0.0035 drop compared to the original FPS.