A Streaming Data Delaunay Triangulation Algorithm Based on Parallel Computing

This paper presents a streaming data algorithm to execute Delaunay triangulations with large LiDAR point clouds(a billion data points) based on multi-core processor architecture.The algorithm combines divide-and-conquer triangulation with streaming data.A quad-tree structure is used to partition the LiDAR data into subnets adaptively,and schedules triangulation and merging of the subnet data into different processors for load balancing.Parallel computing on multi-core processor architecture makes this algorithm highly efficient with a low memory footprint.