Red–green refinement of simplicial meshes in 𝑑 dimensions

Grande, Jörg

doi:10.1090/mcom/3383

Red–green refinement of simplicial meshes in $d$ dimensions
HTML articles powered by AMS MathViewer

by Jörg Grande;

Math. Comp. 88 (2019), 751-782

DOI: https://doi.org/10.1090/mcom/3383

Published electronically: October 9, 2018

HTML | PDF

Abstract:

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.

References

Randolph E. Bank, Andrew H. Sherman, and Alan Weiser, Refinement algorithms and data structures for regular local mesh refinement, Scientific computing (Montreal, Que., 1982) IMACS Trans. Sci. Comput., I, IMACS, New Brunswick, NJ, 1983, pp. 3–17. MR 751598
P. Bastian, K. Birken, K. Johannsen, S. Lang, N. Neuß, 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, doi:10.1007/s007910050003.
Marek Behr, Simplex space-time meshes in finite element simulations, Internat. J. Numer. Methods Fluids 57 (2008), no. 9, 1421–1434. MR 2435099, DOI 10.1002/fld.1796
Marshall Bern and David Eppstein, Mesh generation and optimal triangulation, Computing in Euclidean geometry, Lecture Notes Ser. Comput., vol. 1, World Sci. Publ., River Edge, NJ, 1992, pp. 23–90. MR 1239190, DOI 10.1142/9789814355858_{0}002
J. Bey, Tetrahedral grid refinement, Computing 55 (1995), no. 4, 355–378 (English, with English and German summaries). MR 1370107, DOI 10.1007/BF02238487
Jürgen Bey, Finite-Volumen- und Mehrgitter-Verfahren für elliptische Randwertprobleme, Advances in Numerical Mathematics, B. G. Teubner, Stuttgart, 1998 (German, with German summary). MR 1649911, DOI 10.1007/978-3-663-10071-3
Folkmar Bornemann, Bodo Erdmann, and Ralf Kornhuber, Adaptive multilevel methods in three space dimensions, Internat. J. Numer. Methods Engrg. 36 (1993), no. 18, 3187–3203. MR 1236370, DOI 10.1002/nme.1620361808
Arne Brøndsted, An introduction to convex polytopes, Graduate Texts in Mathematics, vol. 90, Springer-Verlag, New York-Berlin, 1983. MR 683612
Eberhard Bänsch, Local mesh refinement in $2$ and $3$ dimensions, Impact Comput. Sci. Engrg. 3 (1991), no. 3, 181–191. MR 1141298, DOI 10.1016/0899-8248(91)90006-G
P. G. Ciarlet and J.-L. Lions (eds.), Handbook of numerical analysis. Vol. II, Handbook of Numerical Analysis, II, North-Holland, Amsterdam, 1991. Finite element methods. Part 1. MR 1115235
H. S. M. Coxeter, Discrete groups generated by reflections, Ann. of Math. (2) 35 (1934), no. 3, 588–621. MR 1503182, DOI 10.2307/1968753
Jesús A. De Loera, Jörg Rambau, and Francisco Santos, Triangulations, Algorithms and Computation in Mathematics, vol. 25, Springer-Verlag, Berlin, 2010. Structures for algorithms and applications. MR 2743368, DOI 10.1007/978-3-642-12971-1
H. Edelsbrunner and D. R. Grayson, Edgewise subdivision of a simplex, Discrete Comput. Geom. 24 (2000), no. 4, 707–719. ACM Symposium on Computational Geometry (Miami, FL, 1999). MR 1799608, DOI 10.1145/304893.304897
Kenneth Eriksson and Claes Johnson, Adaptive finite element methods for parabolic problems. I. A linear model problem, SIAM J. Numer. Anal. 28 (1991), no. 1, 43–77. MR 1083324, DOI 10.1137/0728003
IEEE Working Group for Floating-Point Arithmetic, IEEE standard for floating-point arithmetic, no. 754-2008, IEEE, New York, 2008, doi:10.1109/IEEESTD.2008.4610935.
Hans Freudenthal, Simplizialzerlegungen von beschränkter Flachheit, Ann. of Math. (2) 43 (1942), 580–582 (German). MR 7105, DOI 10.2307/1968813
Ewgenij Gawrilow and Michael Joswig, polymake: a framework for analyzing convex polytopes, Polytopes—combinatorics and computation (Oberwolfach, 1997) DMV Sem., vol. 29, Birkhäuser, Basel, 2000, pp. 43–73. MR 1785292
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.
Branko Grünbaum, Convex polytopes, Pure and Applied Mathematics, Vol. 16, Interscience Publishers John Wiley & Sons, Inc., New York, 1967. With the cooperation of Victor Klee, M. A. Perles and G. C. Shephard. MR 226496
W. Hackbusch, Multigrid Methods and Applications, Springer Series in Computational Mathematics, vol. 4, Springer-Verlag, Berlin, 1985, doi:10.1007/978-3-662-02427-0.
Thomas J. R. Hughes and Gregory M. Hulbert, Space-time finite element methods for elastodynamics: formulations and error estimates, Comput. Methods Appl. Mech. Engrg. 66 (1988), no. 3, 339–363. MR 928689, DOI 10.1016/0045-7825(88)90006-0
H. W. Kuhn, Some combinatorial lemmas in topology, IBM J. Res. Develop. 4 (1960), 508–524. MR 124038, DOI 10.1147/rd.45.0518
Anwei Liu and Barry Joe, Quality local refinement of tetrahedral meshes based on $8$-subtetrahedron subdivision, Math. Comp. 65 (1996), no. 215, 1183–1200. MR 1348045, DOI 10.1090/S0025-5718-96-00748-X
Joseph M. Maubach, Local bisection refinement for $n$-simplicial grids generated by reflection, SIAM J. Sci. Comput. 16 (1995), no. 1, 210–227. MR 1311687, DOI 10.1137/0916014
Kurt Mehlhorn and Peter Sanders, Algorithms and data structures, Springer-Verlag, Berlin, 2008. The basic toolbox. MR 2444537
Jean-Marie Mirebeau and Albert Cohen, Greedy bisection generates optimally adapted triangulations, Math. Comp. 81 (2012), no. 278, 811–837. MR 2869038, DOI 10.1090/S0025-5718-2011-02459-2
William F. Mitchell, A comparison of adaptive refinement techniques for elliptic problems, ACM Trans. Math. Software 15 (1989), no. 4, 326–347 (1990). MR 1062496, DOI 10.1145/76909.76912
D. Moore, Subdividing simplices, Graphics Gems III (David Kirk, ed.), Academic Press Professional, Inc., San Diego, CA, USA, 1992, pp. 244–249.
Jacob E. Goodman and Joseph O’Rourke (eds.), Handbook of discrete and computational geometry, CRC Press Series on Discrete Mathematics and its Applications, CRC Press, Boca Raton, FL, 1997. MR 1730156
The CGAL Project, CGAL User and Reference Manual, 4.9 ed., CGAL Editorial Board, 2016.
María-Cecilia Rivara, Design and data structure of fully adaptive, multigrid, finite-element software, ACM Trans. Math. Software 10 (1984), no. 3, 242–264. MR 791990, DOI 10.1145/1271.1274
María-Cecilia Rivara and Gabriel Iribarren, The $4$-triangles longest-side partition of triangles and linear refinement algorithms, Math. Comp. 65 (1996), no. 216, 1485–1502. MR 1361811, DOI 10.1090/S0025-5718-96-00772-7
Rob Stevenson, The completion of locally refined simplicial partitions created by bisection, Math. Comp. 77 (2008), no. 261, 227–241. MR 2353951, DOI 10.1090/S0025-5718-07-01959-X
Michael J. Todd, The computation of fixed points and applications, Lecture Notes in Economics and Mathematical Systems, Vol. 124, Springer-Verlag, Berlin-New York, 1976. MR 410732
C. T. Traxler, An algorithm for adaptive mesh refinement in $n$ dimensions, Computing 59 (1997), no. 2, 115–137. MR 1475530, DOI 10.1007/BF02684475