Delaunay refinement algorithms for triangular mesh generation. (English) Zbl 1016.68139

Summary: Delaunay refinement is a technique for generating unstructured meshes of triangles for use in interpolation, the finite element method, and the finite volume method. In theory and practice, meshes produced by Delaunay refinement satisfy guaranteed bounds on angles, edge lengths, the number of triangles, and the grading of triangles from small to large sizes. This article presents an intuitive framework for analyzing Delaunay refinement algorithms that unifies the pioneering mesh generation algorithms of L. Paul Chew and Jim Ruppert, improves the algorithms in several minor ways, and most importantly, helps to solve the difficult problem of meshing nonmanifold domains with small angles.
Although small angles inherent in the input geometry cannot be removed, one would like to triangulate a domain without creating any new small angles. Unfortunately, this problem is not always soluble. A compromise is necessary. A Delaunay refinement algorithm is presented that can create a mesh in which most angles are \(30^\circ\) or greater and no angle is smaller than \(\arcsin[(\sqrt{3}/2)\sin(\phi/2)]\sim (\sqrt{3}/4)\phi\), where \(\phi\leq 60^\circ\) is the smallest angle separating two segments of the input domain. New angles smaller than \(30^\circ\) appear only near input angles smaller than \(60^\circ\). In practice, the algorithm’s performance is better than these bounds suggest.
Another new result is that Ruppert’s analysis technique can be used to reanalyze one of Chew’s algorithms. Chew proved that his algorithm produces no angle smaller than \(30^\circ\) (barring small input angles), but without any guarantees on grading or number of triangles. He conjectures that his algorithm offers such guarantees. His conjecture is conditionally confirmed here: if the angle bound is relaxed to less than \(26.5^\circ\), Chew’s algorithm produces meshes (of domains without small input angles) that are nicely graded and size-optimal.


68U05 Computer graphics; computational geometry (digital and algorithmic aspects)


Full Text: DOI


[1] Babuška, I.; Aziz, A.K., On the angle condition in the finite element method, SIAM J. numer. anal., 13, 2, 214-226, (1976) · Zbl 0324.65046
[2] Baker, B.S.; Grosse, E.; Rafferty, C.S., Nonobtuse triangulation of polygons, Discrete comput. geom., 3, 2, 147-168, (1988) · Zbl 0634.57012
[3] de Berg, M.; van Kreveld, M.; Overmars, M.; Schwarzkopf, O., Computational geometry: algorithms and applications, (1997), Springer-Verlag Berlin
[4] Bern, M.; Eppstein, D., Mesh generation and optimal triangulation, (), 23-90
[5] Bern, M.; Eppstein, D.; Gilbert, J.R., Provably good mesh generation, J. comput. system sci., 48, 3, 384-409, (1994) · Zbl 0799.65119
[6] Bowyer, A., Computing Dirichlet tessellations, Computer J., 24, 2, 162-166, (1981)
[7] Carey, G.F.; Oden, J.T., Finite elements: computational aspects, (1984), Prentice-Hall Englewood Cliffs, NJ · Zbl 0558.73064
[8] Chew, L.P., Constrained Delaunay triangulations, Algorithmica, 4, 1, 97-108, (1989) · Zbl 0664.68042
[9] Chew, L.P., Guaranteed-quality triangular meshes, tech. rept. TR-89-983, (1989), Department of Computer Science, Cornell University Ithaca, NY
[10] Chew, L.P., Guaranteed-quality mesh generation for curved surfaces, (), 274-280
[11] Chew, L.P., Guaranteed-quality Delaunay meshing in 3D, (), 391-393
[12] Clarkson, K.L.; Shor, P.W., Applications of random sampling in computational geometry, II, Discrete comput. geom., 4, 1, 387-421, (1989) · Zbl 0681.68060
[13] Dey, T.K.; Bajaj, C.L.; Sugihara, K., On good triangulations in three dimensions, Internat. J. comput. geom. appl., 2, 1, 75-95, (1992) · Zbl 0761.68095
[14] Devillers, O., On deletion in Delaunay triangulations, (), 181-188
[15] Dwyer, R.A., A faster divide-and-conquer algorithm for constructing Delaunay triangulations, Algorithmica, 2, 2, 137-151, (1987) · Zbl 0631.68043
[16] Frey, W.H., Selective refinement: A new strategy for automatic node placement in graded triangular meshes, Internat. J. numer. methods engrg., 24, 11, 2183-2200, (1987) · Zbl 0621.73098
[17] Guibas, L.J.; Stolfi, J., Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams, ACM trans. graphics, 4, 2, 74-123, (1985) · Zbl 0586.68059
[18] Jones, M.T.; Plassmann, P.E., Adaptive refinement of unstructured finite-element meshes, Finite elements in analysis and design, 25, 41-60, (1997) · Zbl 0897.65074
[19] Lawson, C.L., Software for C1 surface interpolation, (), 161-194
[20] Lee, D.-T.; Lin, A.K., Generalized Delaunay triangulations for planar graphs, Discrete comput. geom., 1, 201-217, (1986) · Zbl 0596.52007
[21] Lee, D.-T.; Schachter, B.J., Two algorithms for constructing a Delaunay triangulation, Internat. J. comput. inform. sci., 9, 3, 219-242, (1980) · Zbl 0441.68047
[22] Miller, G.L.; Talmor, D.; Teng, S.-H., Optimal good-aspect-ratio coarsening for unstructured meshes, (), 538-547 · Zbl 1321.65152
[23] Miller, G.L.; Talmor, D.; Teng, S.-H.; Walkington, N., A Delaunay based numerical method for three dimensions: generation, formulation, and partition, (), 683-692 · Zbl 0978.68575
[24] Mitchell, S.A., Cardinality bounds for triangulations with bounded minimum angle, (), 326-331
[25] Ruppert, J., A new and simple algorithm for quality 2-dimensional mesh generation, tech. rept. UCB/CSD 92/694, (1992), University of California at Berkeley Berkeley, CA
[26] Ruppert, J., A new and simple algorithm for quality 2-dimensional mesh generation, (), 83-92 · Zbl 0801.68163
[27] Ruppert, J., A Delaunay refinement algorithm for quality 2-dimensional mesh generation, J. algorithms, 18, 3, 548-585, (1995) · Zbl 0828.68122
[28] Seidel, R., Backwards analysis of randomized geometric algorithms, tech. rept. TR-92-014, (1992), International Computer Science Institute, University of California at Berkeley Berkeley, CA
[29] Shewchuk, J.R., Triangle: engineering a 2D quality mesh generator and Delaunay triangulator, (), 203-222
[30] Shewchuk, J.R., Tetrahedral mesh generation by Delaunay refinement, (), 86-95
[31] Shewchuk, J.R., Mesh generation for domains with small angles, (), 1-10 · Zbl 1378.65064
[32] Watson, D.F., Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes, Computer J., 24, 2, 167-172, (1981)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.