Incremental construction of the delaunay triangulation and the delaunay graph in medium dimension

ABSTRACT

We describe a new implementation of the well-known incremental algorithm for constructing Delaunay triangulations in any dimension. Our implementation follows the exact computing paradigm and is fully robust. Extensive comparisons show that our implementation outperforms the best currently available codes for exact convex hulls and Delaunay triangulations, compares very well to the fast non-exact QHull implementation and can be used for quite big input sets in spaces of dimensions up to 6. To circumvent prohibitive memory usage, we also propose a modification of the algorithm that uses and stores only the Delaunay graph (the edges of the full triangulation). We show that a careful implementation of the modified algorithm performs only 6 to 8 times slower than the original algorithm while drastically reducing memory usage in dimension 4 or above.

REFERENCES

• 1: Nina Amenta , Sunghee Choi , Günter Rote, Incremental constructions con BRIO, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA [doi>10.1145/777792.777824]
• 2: D. K. Blandford, G. E. Blelloch, D. E. Cardoze, and C. Kadow. Compact representations of simplicial meshes in two and three dimensions. In Proc. 12th International Meshing Roundtable, pages 135--146, 2003.
• 3: Daniel K. Blandford , Guy E. Blelloch , Ian A. Kash, Compact representations of separable graphs, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 4: C. E. Board. CGAL User and Reference Manual, 3.3 edition, 2007.
• 5: J.-D. Boissonnat, O. Devillers, S. Pion, M. Teillaud, and M. Yvinec. Triangulations in CGAL. Comput. Geom. Theory Appl., 22:5--19, 2002.
• 6: Jean-Daniel Boissonnat , Monique Teillaud, On the randomized construction of the Delaunay tree, Theoretical Computer Science, v.112 n.2, p.339-354, May 10, 1993 [doi>10.1016/0304-3975(93)90024-N]
• 7: Hervé Brönnimann , Christoph Burnikel , Sylvain Pion, Interval arithmetic yields efficient dynamic filters for computational geometry, Discrete Applied Mathematics, v.109 n.1-2, p.25-47, April 15, 2001 [doi>10.1016/S0166-218X(00)00231-6]
• 8: A. R. Butz, Alternative Algorithm for Hilbert's Space-Filling Curve, IEEE Transactions on Computers, v.20 n.4, p.424-426, April 1971 [doi>10.1109/T-C.1971.223258]
• 9: Kenneth L. Clarkson , Kurt Mehlhorn , Raimund Seidel, Four results on randomized incremental constructions, Computational Geometry: Theory and Applications, v.3 n.4, p.185-212, Sept. 1993 [doi>10.1016/0925-7721(93)90009-U]
• 10: C. Delage. Spatial sorting. In C. E. Board, editor, CGAL User and Reference Manual. www.cgal.org, 3.3 edition, 2007.
• 11: Erik D. Demaine , Alejandro López-Ortiz , J. Ian Munro, Adaptive set intersections, unions, and differences, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.743-752, January 09-11, 2000, San Francisco, California, United States
• 12: O. Devillers, S. Pion, and M. Teillaud. Walking in a triangulation. Internat. J. Found. Comput. Sci., 13:181--199, 2002.
• 13: Rex A. Dwyer, Higher-dimensional Voronoi diagrams in linear expected time, Discrete & Computational Geometry, v.6 n.4, p.343-367, 1991 [doi>10.1007/BF02574694]
• 14: M. Hemmer, S. Hert, L. Kettner, S. Pion, and S. Schirra. Number types. In C. E. Board, editor, CGAL User and Reference Manual. CGAL, 3.3 edition, 2007.
• 15: S. Hornus and J.-D. Boissonnat. An efficient implementation of delaunay triangulations in medium dimensions. Research Report 6743, INRIA, 2008. http://hal.inria.fr/inria-00343188.
• 16: Martin Isenburg , Yuanxin Liu , Jonathan Shewchuk , Jack Snoeyink, Streaming computation of Delaunay triangulations, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 17: Guohua Jin , John Mellor-Crummey, SFCGen: A framework for efficient generation of multi-dimensional space-filling curves by recursion, ACM Transactions on Mathematical Software (TOMS), v.31 n.1, p.120-148, March 2005 [doi>10.1145/1055531.1055537]
• 18: Marcelo Kallmann , Daniel Thalmann, Star-vertices: a compact representation for planar meshes with adjacency information, Journal of Graphics Tools, v.6 n.1, p.7-18, September 2001
• 19: P. Kumar and E. A. Ramos. I/O-efficient construction of Voronoi diagrams. Technical report, Max Planck Institute Informatik, Saarbrücken, 2002.
• 20: M. Maciejewski, S. Colombi, C. Alard, F. Bouchet, and C. Pichon. Phase-space structures I: A comparison of 6D density estimators. http://arxiv.org/abs/0810.0504v1, Oct. 2008.
• 21: K. Mulmuley. Computational Geometry: An Introduction Through Randomized Algorithms. Prentice Hall, 1994.
• 22: W. E. Schaap. DTFE: the Delaunay Tessellation Field Estimator. PhD thesis, University of Groningen, 2007. http://irs.ub.rug.nl/ppn/298831376.
• 23: Jonathan Richard Shewchuk, Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator, Selected papers from the Workshop on Applied Computational Geormetry, Towards Geometric Engineering, p.203-222, May 27-28, 1996

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.8 Metrics
          Subjects: Performance measures

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms, Experimentation, Performance

Keywords:
Delaunay graph, Delaunay triangulation