Title: Streaming computation of Delaunay triangulations
Abstract: We show how to greatly accelerate algorithms that compute Delaunay triangulations of huge, well-distributed point sets in 2D and 3D by exploiting the natural spatial coherence in a stream of points. We achieve large performance gains by introducing spatial finalization into point streams: we partition space into regions, and augment a stream of input points with finalization tags that indicate when a point is the last in its region. By extending an incremental algorithm for Delaunay triangulation to use finalization tags and produce streaming mesh output, we compute a billion-triangle terrain representation for the Neuse River system from 11.2 GB of LIDAR data in 48 minutes using only 70 MB of memory on a laptop with two hard drives. This is a factor of twelve faster than the previous fastest out-of-core Delaunay triangulation software.
Publication Year: 2006
Publication Date: 2006-07-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 137
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot