2007.09.03 | Gerth Stølting Brodal

Streaming Computation of Delaunay Triangulations
Jonathan Richard Shewchuk
Computer Science Division
University of California at Berkeley

We show how to compute Delaunay triangulations of utterly huge,
well-distributed point sets in 2D and 3D on an ordinary computer 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.