Red-green refinement of simplicial meshes in \(d\) dimensions. (English) Zbl 1497.65154

Summary: The local red-green mesh refinement of consistent, simplicial meshes in \( d\) dimensions is considered. We give a constructive solution to the green closure problem in arbitrary dimension \( d\). Suppose that \( \mathcal {T}\) is a simplicial mesh and that \( R\) is an arbitrary subset of its faces, which is refined with the Coxeter-Freudenthal-Kuhn (red) refinement rule. Green refinements of simplices \( S\in \mathcal {T}\) are generated to restore the consistency of the mesh using a particular placing triangulation. No new vertices are created in this process. The green refinements are consistent with the red refinement on \( R\), the unrefined mesh regions, and all other neighboring green refinements.


65M50 Mesh generation, refinement, and adaptive methods for the numerical solution of initial value and initial-boundary value problems involving PDEs
65N50 Mesh generation, refinement, and adaptive methods for boundary value problems involving PDEs
65D18 Numerical aspects of computer graphics, image analysis, and computational geometry


DROPS; UG; polymake; CGAL
Full Text: DOI


[1] Bank, Randolph E.; Sherman, Andrew H.; Weiser, Alan, Refinement algorithms and data structures for regular local mesh refinement. Scientific computing, Montreal, Que., 1982, IMACS Trans. Sci. Comput., I, 3-17 (1983), IMACS, New Brunswick, NJ
[2] bastian1997 P. Bastian, K. Birken, K. Johannsen, S. Lang, N. Neu\ss , H. Rentz-Reichert, and C. Wieners, UG – a flexible software toolbox for solving partial differential equations, Computing and Visualization in Science 1 (1997), no. 1, 27-40, http://dx.doi.org/10.1007/s007910050003doi:10.1007/s007910050003. · Zbl 0970.65129
[3] Behr, Marek, Simplex space-time meshes in finite element simulations, Internat. J. Numer. Methods Fluids, 57, 9, 1421-1434 (2008) · Zbl 1145.65070
[4] Bern, Marshall; Eppstein, David, Mesh generation and optimal triangulation. Computing in Euclidean geometry, Lecture Notes Ser. Comput. 1, 23-90 (1992), World Sci. Publ., River Edge, NJ
[5] Bey, J., Tetrahedral grid refinement, Computing, 55, 4, 355-378 (1995) · Zbl 0839.65135
[6] Bey, J\`“urgen, Finite-Volumen- und Mehrgitter-Verfahren f\'”ur elliptische Randwertprobleme, Advances in Numerical Mathematics, 356 pp. (1998), B. G. Teubner, Stuttgart · Zbl 0906.65120
[7] Bornemann, Folkmar; Erdmann, Bodo; Kornhuber, Ralf, Adaptive multilevel methods in three space dimensions, Internat. J. Numer. Methods Engrg., 36, 18, 3187-3203 (1993) · Zbl 0780.73073
[8] Br\o ndsted, Arne, An Introduction to Convex Polytopes, Graduate Texts in Mathematics 90, viii+160 pp. (1983), Springer-Verlag, New York-Berlin · Zbl 0509.52001
[9] B\"ansch, Eberhard, Local mesh refinement in \(2\) and \(3\) dimensions, Impact Comput. Sci. Engrg., 3, 3, 181-191 (1991) · Zbl 0744.65074
[10] Handbook of Numerical Analysis. Vol. II, Handbook of Numerical Analysis, II, x+928 pp. (1991), North-Holland, Amsterdam
[11] Coxeter, H. S. M., Discrete groups generated by reflections, Ann. of Math. (2), 35, 3, 588-621 (1934) · Zbl 0010.01101
[12] De Loera, Jes\'us A.; Rambau, J\"org; Santos, Francisco, Triangulations, Algorithms and Computation in Mathematics 25, xiv+535 pp. (2010), Springer-Verlag, Berlin · Zbl 1207.52002
[13] Edelsbrunner, H.; Grayson, D. R., Edgewise subdivision of a simplex, Discrete Comput. Geom., 24, 4, 707-719 (2000) · Zbl 0968.51016
[14] Eriksson, Kenneth; Johnson, Claes, Adaptive finite element methods for parabolic problems. I. A linear model problem, SIAM J. Numer. Anal., 28, 1, 43-77 (1991) · Zbl 0732.65093
[15] ieee754-2008 IEEE Working Group for Floating-Point Arithmetic, IEEE standard for floating-point arithmetic, no. 754-2008, IEEE, New York, 2008, http://dx.doi.org/10.1109/IEEESTD.2008.4610935doi:10.1109/IEEESTD.2008.4610935.
[16] Freudenthal, Hans, Simplizialzerlegungen von beschr\"ankter Flachheit, Ann. of Math. (2), 43, 580-582 (1942) · Zbl 0060.40701
[17] Gawrilow, Ewgenij; Joswig, Michael, Polymake: A Framework for Analyzing Convex Polytopes. Polytopes-combinatorics and computation, Oberwolfach, 1997, DMV Sem. 29, 43-73 (2000), Birkh\"auser, Basel · Zbl 0960.68182
[18] drops-report:2002 S. Gro, J. Peters, V. Reichelt, and A. Reusken, The DROPS package for numerical simulations of incompressible flows using parallel adaptive multigrid techniques, IGPM preprint 211, IGPM, RWTH Aachen University, 2002.
[19] Gr\"unbaum, Branko, Convex Polytopes, With the cooperation of Victor Klee, M. A. Perles and G. C. Shephard. Pure and Applied Mathematics, Vol. 16, xiv+456 pp. (1967), Interscience Publishers John Wiley & Sons, Inc., New York · Zbl 0152.20602
[20] hackbusch1985 W. Hackbusch, Multigrid Methods and Applications, Springer Series in Computational Mathematics, vol. 4, Springer-Verlag, Berlin, 1985, http://dx.doi.org/10.1007/978-3-662-02427-0doi:10.1007/978-3-662-02427-0. · Zbl 0595.65106
[21] Hughes, Thomas J. R.; Hulbert, Gregory M., Space-time finite element methods for elastodynamics: formulations and error estimates, Comput. Methods Appl. Mech. Engrg., 66, 3, 339-363 (1988) · Zbl 0616.73063
[22] Kuhn, H. W., Some combinatorial lemmas in topology, IBM J. Res. Develop., 4, 518-524 (1960) · Zbl 0109.15603
[23] Liu, Anwei; Joe, Barry, Quality local refinement of tetrahedral meshes based on \(8\)-subtetrahedron subdivision, Math. Comp., 65, 215, 1183-1200 (1996) · Zbl 0858.65120
[24] Maubach, Joseph M., Local bisection refinement for \(n\)-simplicial grids generated by reflection, SIAM J. Sci. Comput., 16, 1, 210-227 (1995) · Zbl 0816.65090
[25] Mehlhorn, Kurt; Sanders, Peter, Algorithms and Data Structures, xii+300 pp. (2008), Springer-Verlag, Berlin · Zbl 1146.68069
[26] Mirebeau, Jean-Marie; Cohen, Albert, Greedy bisection generates optimally adapted triangulations, Math. Comp., 81, 278, 811-837 (2012) · Zbl 1252.65043
[27] Mitchell, William F., A comparison of adaptive refinement techniques for elliptic problems, ACM Trans. Math. Software, 15, 4, 326-347 (1990) (1989) · Zbl 0900.65306
[28] moore1992b D. Moore, Subdividing simplices, Graphics Gems III (David Kirk, ed.), Academic Press Professional, Inc., San Diego, CA, USA, 1992, pp. 244-249.
[29] Handbook of Discrete and Computational Geometry, CRC Press Series on Discrete Mathematics and its Applications, xvi+991 pp. (1997), CRC Press, Boca Raton, FL · Zbl 0890.52001
[30] cgal2016 The CGAL Project, CGAL User and Reference Manual, 4.9 ed., CGAL Editorial Board, 2016.
[31] Rivara, Mar\'\i a-Cecilia, Design and data structure of fully adaptive, multigrid, finite-element software, ACM Trans. Math. Software, 10, 3, 242-264 (1984) · Zbl 0578.65112
[32] Rivara, Mar\'\i a-Cecilia; Iribarren, Gabriel, The \(4\)-triangles longest-side partition of triangles and linear refinement algorithms, Math. Comp., 65, 216, 1485-1502 (1996) · Zbl 0853.65096
[33] Stevenson, Rob, The completion of locally refined simplicial partitions created by bisection, Math. Comp., 77, 261, 227-241 (2008) · Zbl 1131.65095
[34] Todd, Michael J., The Computation of Fixed Points and Applications, vii+129 pp. (1976), Springer-Verlag, Berlin-New York
[35] Traxler, C. T., An algorithm for adaptive mesh refinement in \(n\) dimensions, Computing, 59, 2, 115-137 (1997) · Zbl 0944.65123
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.