This article proposes a robust and scalable clustering method for 3D point-cloud plane segmentation with applications in Micro Aerial Vehicles (MAVs), such as Simultaneous Localization and Mapping (SLAM), collision avoidance, and object detection. Our approach builds on the sparse subspace clustering framework, which seeks a collection of subspaces that fit the data. Since subspace clustering requires solving a global sparse representation problem and forming a similarity graph, its high computational complexity is known to be a significant drawback, and performance is sensitive to a few hyperparameters. To tackle these challenges, our method has two key ingredients. We use randomized sampling to accelerate subspace clustering by solving a reduced optimization problem. We also analyze the obtained segmentation for quality assurance and performing a post-processing process to resolve two forms of model mismatch. We present numerical experiments to demonstrate the benefits and merits of our method. © 2021 IEEE.