In construction environments, laser-scanning technologies can perform rapid spatial data collection to monitor construction progress, control construction quality, and support decisions about how to streamline field activities. However, even experienced surveyors cannot guarantee comprehensive laser scanning data collection in the field due to its constantly changing environment, wherein a large number of objects are subject to different data-quality requirements. The current practice of manually planned laser scanning often produces data of insufficient coverage, accuracy, and details. While redundant data collection can improve data quality, this process can also be inefficient and time-consuming. There are many studies on automatic sensor planning methods for guided laser-scanning data collection in the literature. However, fewer studies exist on how to handle exponentially large search space of laser scan plans that consider data quality requirements, such as accuracy and levels of details (LOD). This paper presents a rapid laser scan planning method that overcomes the computational complexity of planning laser scans based on diverse data quality requirements in the field. The goal is to minimize data collection time, while ensuring that the data quality requirements of all objects are satisfied. An analytical sensor model of laser scanning is constructed to create a "divide-and-conquer" strategy for rapid laser scan planning of dynamic environments wherein a graph is generated having specific data quality requirements (e.g., levels of accuracy and detail of certain objects) in terms of nodes and spatial relationships between these requirements as edges (e.g., distance, line-of-sight). A graph-coloring algorithm then decomposes the graph into sub-graphs and identifies "local" optimal laser scan plans of these sub-graphs. A solution aggregation algorithm then combines the local optimal plans to generate a plan for the entire site. Runtime analysis shows that the computation time of the proposed method does not increase exponentially with site size. Validation results of multiple case studies show that the proposed laser scan planning method can produce laser-scanning data with higher quality than data collected by experienced professionals, and without increasing the data collection time.