Efficient 3D scanning technology has led to acquisition of very large datasets for application areas such as terrain and urban modeling. However, relatively few techniques exist to automatically extract meaningful regions from this data, and the largest datasets examined in the literature rarely exceed millions of points in size. In this paper, we present an efficient algorithm for identification of locally planar regions in large-scale GPS-registered scan data. Utilizing a high-end multiprocessor machine, we are able to process scan data of approximately 100 million points, obtained on a college campus, in just over 20 minutes.