“Streaming computation of Delaunay triangulations” by Isenburg, Liu, Shewchuk and Snoeyink

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.

1. Agarwal, P. K., Arge, L., and Yi, K. 2005. I/O-efficient construction of constrained Delaunay triangulations. In Proceedings of the Thirteenth European Symposium on Algorithms, 355–366.]] Google ScholarDigital Library
2. Amenta, N., Choi, S., and Rote, G. 2003. Incremental constructions con BRIO. In Proceedings of the Nineteenth Annual Symposium on Computational Geometry, Association for Computing Machinery, San Diego, California, 211–219.]] Google ScholarDigital Library
3. Blandford, D. K., Blelloch, G. E., Cardoze, D. E., and Kadow, C. 2005. Compact representations of simplicial meshes in two and three dimensions. International Journal of Computational Geometry and Applications 15, 1 (Feb.), 3–24.]]Google ScholarCross Ref
4. Blelloch, G. E., Hardwick, J. C., Miller, G. L., and Talmor, D. 1999. Design and implementation of a practical parallel Delaunay algorithm. Algorithmica 24, 3–4 (Aug.), 243–269.]]Google ScholarCross Ref
5. Bowyer, A. 1981. Computing Dirichlet tessellations. Computer Journal 24, 2, 162–166.]]Google ScholarCross Ref
6. Buchin, K. 2005. Constructing Delaunay triangulations along space-filling curves. In Second Symposium on Voronoi Diagrams, 184–195.]]Google Scholar
7. Cignoni, P., Montani, C., and Scopigno, R. 1998. DeWall: A fast divide and conquer Delaunay triangulation algorithm in Ed. Computer-Aided Design 30, 5 (Apr.), 333–341.]]Google ScholarCross Ref
8. Clarkson, K. L., and Shor, P. W. 1989. Applications of random sampling in computational geometry, II. Discrete & Computational Geometry 4, 1, 387–421.]]Google ScholarDigital Library
9. Clarkson, K. L. 1988. A randomized algorithm for closest-point queries. SIAM Journal on Computing 17, 4 (Aug.), 830–847.]] Google ScholarDigital Library
10. Fortune, S. 1992. Voronoi diagrams and Delaunay triangulations. In Computing in Euclidean Geometry, D.-Z. Du and F. Hwang, Eds., vol. 1 of Lecture Notes Series on Computing. World Scientific, Singapore, 193–233.]]Google Scholar
11. Frederick, C. O., Wong, Y. C., and Edge, F. W. 1970. Two-dimensional automatic mesh generation for structural analysis. International Journal for Numerical Methods in Engineering 2, 133–144.]]Google ScholarCross Ref
12. Isenburg, M., and Gumhold, S. 2003. Out-of-core compression for gigantic polygon meshes. ACM Transactions on Graphics 22, 3 (July), 935–942.]] Google ScholarDigital Library
13. Isenburg, M., and Lindstrom, P. 2005. Streaming meshes. In Visualization ’05 Proceedings, 231–238.]]Google Scholar
14. Isenburg, M., Lindstrom, P., Gumhold, S., and Snoeyink, J. 2003. Large mesh simplification using processing sequences. In Visualization ’03, 465–472.]] Google ScholarDigital Library
15. Karp, R. M. 1992. On-line algorithms versus off-line algorithms: How much is it worth to know the future? In IFIP 12th World Computer Congress, North-Holland, J. van Leeuwen, Ed., vol. A-12 of IFIP Transactions, 416–429.]] Google ScholarDigital Library
16. Katajainen, J., and Koppinen, M. 1988. Constructing Delaunay triangulations by merging buckets in quadtree order. Fundamenta Informaticae XI, 11, 275–288.]]Google Scholar
17. Kumar, P. 2003. Cache oblivious algorithms. In Algorithms for Memory Hierarchies, LNCS 2625, U. Meyer, P. Sanders, and J. Sibeyn, Eds. Springer-Verlag, 193–212.]]Google Scholar
18. Lawson, C. L. 1977. Software for C1 surface interpolation. In Mathematical Software III, J. R. Rice, Ed. Academic Press, New York, 161–194.]]Google Scholar
19. Liu, Y., and Snoeyink, J. 2005. A comparison of five implementations of 3D Delaunay tessellation. In Combinatorial and Computational Geometry, vol. 52 of MSRI Publications. Cambridge, 435–453.]]Google Scholar
20. Okabe, A., Boots, B., Sugihara, K., and Chiu, S. N. 2000. Spatial tessellations: Concepts and applications of Voronoi diagrams, 2nd ed. Wiley, New York.]] Google ScholarDigital Library
21. Pajarola, R. 2005. Stream-processing points. In Visualization ’05 Proc., 239–246.]]Google Scholar
22. Quillin, M., 2002. Flood plain maps better, but late—years late, March 11. Raleigh News & Observer.]]Google Scholar
23. Shaffer, C. A. 1990. Fast circle-rectangle intersection checking. In Graphics Gems. Academic Press Professional, Inc., San Diego, CA, USA, 51–53.]] Google ScholarDigital Library
24. Shamos, M. I., and Hoey, D. 1975. Closest-point problems. In 16th Annual Symposium on Foundations of Computer Science, IEEE Press, 151–162.]]Google Scholar
25. Shewchuk, J. R. 1996. Triangle: Engineering a 2D quality mesh generator and Delaunay triangulator. In Applied Computational Geometry: Towards Geometric Engineering, M. C. Lin and D. Manocha, Eds., vol. 1148 of Lecture Notes in Computer Science. Springer-Verlag, Berlin, May, 203–222.]] Google ScholarDigital Library
26. Shewchuk, J. R. 1997. Adaptive precision floating-point arithmetic and fast robust geometric predicates. Discrete & Computational Geometry 18, 3 (Oct.), 305–363.]]Google Scholar
27. Shewchuk, J. R. 1998. Tetrahedral mesh generation by Delaunay refinement. In Proceedings of the Fourteenth Annual Symposium on Computational Geometry, Association for Computing Machinery, Minneapolis, Minnesota, 86–95.]] Google ScholarDigital Library
28. Su, P., and Drysdale, R. L. S. 1995. A comparison of sequential Delaunay triangulation algorithms. In Proceedings of the Eleventh Annual Symposium on Computational Geometry, 61–70.]] Google ScholarDigital Library
29. Vitter, J. S. 2001. External memory algorithms and data structures: Dealing with MASSIVE data. ACM Computing Surveys 33, 2, 209–271.]] Google ScholarDigital Library
30. Watson, D. F. 1981. Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes. Computer Journal 24, 2, 167–172.]]Google ScholarCross Ref
31. Yoon, S., Lindstrom, P., Pascucci, V., and Manocha, D. 2005. Cache-oblivious mesh layouts. ACM Transactions on Graphics 24, 3 (July), 886–893.]] Google ScholarDigital Library