Streaming Computation of Delaunay Triangulations (fragment 2)

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

Unit 8. Conclusion

Task 4. Translate the abstracts, mind the style (scientific)

Task 3. Find the linking words, add them into the table

Task 1. Read the following conclusion to the article. Translate the words in italics. Fill in the table below:

Martin Isenburg, Yuanxin Liu, Jonathan Shewchuk, Jack Snoeyink

Researchers with whom we have discussed out-of-core Delaunay triangulation suggest, almost by reflex, sorting the points first. For data sets with no spatial coherence at all, we too advocate sorting. But in our experience, large, real-world data sets have plenty of patial coherence. The power of exploiting that spatial coherence is perhaps best illustrated by two facts. First, it takes Agarwal et al. [2005] three hours to Hilbert sort the same point set we triangulate in 48 minutes. Second, our triangulator runs as quickly on the original Neuse point data as on the Hilbert-sorted Neuse points, which were both kindly provided by Agarwal et al. [2005].

We realize the benefits of sorting, at much less cost, by documenting the existing spatial coherence with spatial finalization and enhancing it by reordering points. In analogy to aikido, we use the data's spatial coherence to control and direct the data with small efforts, rather than fight it head on (by sorting it). One advantage is speed. Another advantage is that we can visualize the early output of a pipeline of streaming modules soon after starting it. We have described just one method of spatial finalization for point sets. We choose a depth-k quadtree/octree because we can describe it succinctly with a bounding box and integer k, and it is relatively simple to determine which cells a sphere intersects. We believe it is possible to eliminate the first pass of spfinalize by computing a quadtree/octree partitioning adaptively ‑ without advance knowledge of the bounding box ‑ during the second pass. Binary space partitions, k-d trees, and many other spatial subdivisions would work too. If a point stream is sorted along a space-filling curve like a Hilbert or z-order curve, the stream is chunked, and finalization can be implicit ‑ a cell is finalized when the next point leaves it. Sweepline algorithms, such as Fortune's [1992] for Delaunay triangulation, generate a point stream with implicit spatial finalization: they sort the points by one coordinate, thereby partitioning the plane into slabs. At each event, they finalize a slab, and could potentially produce partial output and free data structures. Likewise, Pajarola's [2005] streaming k-neighbor computation finalizes slabs of space with a sweep plane. But these methods bring with them the disadvantages of sorting discussed above. The Achilles' heel of our 3D streaming triangulator is that it performs poorly on point clouds sampled from surfaces. The Delaunay triangulations of these point clouds have many tetrahedra with large circumspheres, which intersect many cells and are thus long-lived. We believe this problem can be solved by using more sophisticated, non-disjoint finalization regions computed by a randomized divide-and-conquer technique of Clarkson [1988]. Clarkson's method covers space with overlapping spherical regions tailored to the point set, and guarantees that each Delaunay circumsphere is covered by a constant number of these regions; yet no region contains too many points. (Agarwal et al. use the same random sampling technique to divide a constrained Delaunay triangulation into subproblems. We propose to use it for spatial finalization instead.) Implementations of traditional 2D divide-and-conquer Delaunay algorithms [Shamos and Hoey 1975] are faster than incremental implementations, and even run in expected linear time on random points from some distributions [Katajainen and Koppinen 1988]. 2D divide-and-conquer algorithms seem amenable to a streaming implementation using our spatial finalization method. The key to fast streaming is to merge adjacent triangulations in an order dictated by the data, instead of an a priori order. Unfortunately, this rules out the best-known generalization of the divide-and-conquer approach to dimensions above two, the Delaunay Wall algorithm [Cignoni et al. 1998], which constructs tetrahedra in an inflexible, predetermined order. We do not know how to create a 3D streaming divide-and-conquer Delaunay algorithm. As huge data sets become ubiquitous in geometry processing, we hope that streaming geometry with finalization information and low width will become common. If point-creating programs would include finalization tags in their output streams, we could pipe them directly to our Delaunay triangulators, and begin producing triangles or tetrahedra even before all the points are created. The advantages of stream processing are so strong that we believe the producers of huge geometric data sets will have a profound incentive to make the modest efforts required to improve their spatial coherence and include finalization information.