Abstract 1. Streaming Computation of Delaunay Triangulations (fragment 1)

Date: 2015-10-07; view: 576.

Task 1. Look at the following abstracts, find their differences and common features. Which abstracts describe the research done? Which abstracts represent the current situation at the scientific field?

Unit 7. Abstracts

Task 3. Translate the text using the vocabulary, mind the sentence structure

Task 2. Look at the words in italics and say what they are used for.

Martin Isenburg University of California at Berkeley

Yuanxin Liu University of North Carolina at Chapel Hill

Jonathan Shewchuk University of California at Berkeley

Jack Snoeyink University of North Carolina at Chapel Hill

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 in to 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.

CR Categories:I.3.5 [COMPUTER GRAPHICS]: Computational Geometry and Object Modeling-Geometric algorithms

Keywords:geometry processing, Delaunay triangulation, stream processing, TIN terrain model, spatial finalization