Nothing Special   »   [go: up one dir, main page]

skip to main content
research-article

Local Bisection Refinement for N-Simplicial Grids Generated by Reflection

Published: 01 January 1995 Publication History

Abstract

A simple local bisection refinement algorithm for the adaptive refinement of n-simplicial grids is presented. The algorithm requires that the vertices of each simplex be ordered in a special way relative to those in neighboring simplices. It is proven that certain regular simplicial grids on $[0,1]^n $ have this property, and the more general grids to which this method is applicable are discussed. The edges to be bisected are determined by an ordering of the simplex vertices, without local or global computation or communication. Further, the number of congruency classes in a locally refined grid turns out to be bounded above by n, independent of the level of refinement. Simplicial grids of higher dimension are frequently used to approximate solution manifolds of parametrized equations, for instance, as in [W. C. Rheinboldt, Numer. Math., 53 (1988), pp. 165–180] and [E. Allgower and K. Georg, Utilitas Math., 16 (1979), pp. 123–129]. They are also used for the determination of fixed points of functions from ${\bf R}^n $ to ${\bf R}^n $, as described in [M. J. Todd, Lecture Notes in Economic and Mathematical Systems, 124, Springer-Verlag, Berlin, 1976]. In two and three dimensions, such grids of triangles, respectively, tetrahedrons, are used for the computation of finite element solutions of partial differential equations, for example, as in [O. Axelsson and V. A. Barker, Finite Element Solution of Boundary Value Problems, Academic Press, Orlando, 1984], [R. E. Bank and B. D. Welfert, SIAM J. Numer. Anal., 28 (1991), pp. 591–623], [W. F. Mitchell, SIAM J. Sci. Statist. Comput., 13 (1992), pp. 146–147], and [M. C. Rivara, J. Comput. Appl. Math., 36 (1991), pp. 79–89]. The new method is applicable to any triangular grid and may possibly be applied to many tetrahedral grids using additional closure refinement to avoid incompatibilities.

References

[1]
Eugene Allgower, Kurt Georg, Generation of triangulations by reflections, Utilitas Math., 16 (1979), 123–129
[2]
David C. Arney, Joseph E. Flaherty, An adaptive mesh-moving and local refinement method for time-dependent partial differential equations, ACM Trans. Math. Software, 16 (1990), 48–71
[3]
O. Axelsson, V. A. Barker, Finite element solution of boundary value problems, Computer Science and Applied Mathematics, Academic Press Inc., Orlando, FL, 1984xviii+432
[4]
E. F. D'Azevedo, Optimal triangular mesh generation by coordinate transformation, SIAM J. Sci. Statist. Comput., 12 (1991), 755–786
[5]
Timothy J. Baker, Developments and trends in three-dimensional mesh generation, Appl. Numer. Math., 5 (1989), 275–304
[6]
Randolph E. Bank, Bruno D. Welfert, A posteriori error estimates for the Stokes problem, SIAM J. Numer. Anal., 28 (1991), 591–623
[7]
Eberhard Bansch, Local mesh refinement in 2 and 3 dimensions, Impact Comput. Sci. Engrg., 3 (1991), 181–191
[8]
M. Bern, D. Eppstein, Mesh generation and optimal triangulation, Technical Report, CSL-92-1, Xerox PARC and University of California, Irvine, 1992
[9]
Marshall Bern, David Eppstein, Frances Yao, The expected extremes in a Delaunay triangulation, Internat. J. Comput. Geom. Appl., 1 (1991), 79–91
[10]
M. Bern, D. Eppstein, J. R. Gilbert, Provably good mesh generation31st Annual Symposium on Foundations of Computer Science, Vol. I, II (St. Louis, MO, 1990), IEEE Comput. Soc. Press, Los Alamitos, CA, 1990, 231–241
[11]
J. Bey, Simplicial grid refinement in three and more dimensions, Technical Report of the Mathematisches Institut, Universität Tübingen, Auf der Morgenstelle 10, D-72076 Tübingen, Germany, in preparation
[12]
S. W. Bova, G. F. Carey, Mesh generation/refinement using fractal concepts and iterated function systems, Internat. J. Numer. Methods Engrg., 33 (1992), 287–305
[13]
Hans Freudenthal, Simplizialzerlegungen von beschränkter Flachheit, Ann. of Math. (2), 43 (1942), 580–582
[14]
William H. Frey, David A. Field, Mesh relaxation: a new technique for improving triangulations, Internat. J. Numer. Methods Engrg., 31 (1991), 1121–1133
[15]
P. L. George, F. Hecht, Automatic mesh generator with specified boundary, Comput. Methods Appl. Mech. Engrg., 92 (1991), 269–288
[16]
D. J. Hebert, Symbolic local refinement of tetrahedral grids, J. Symbolic Comput., 17 (1994), 457–472, Technical Report ICMA-93-181, University of Pittsburgh
[17]
W. D. Henshaw, G. Chesshire, Multigrid on composite meshes, SIAM J. Sci. Statist. Comput., 8 (1987), 914–923
[18]
Donald E. Knuth, The art of computer programming. Volume 3, Sorting and Searching, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1973xi+722 pp. (1 foldout)
[19]
Igor Kossaczky, A recursive approach to local mesh refinement in two and three dimensions, J. Comput. Appl. Math., 55 (1994), 275–288
[20]
Rainald Lohner, Some useful data structures for the generation of unstructured grids, Comm. Appl. Numer. Methods, 4 (1988), 123–135
[21]
J. M. Maubach, Iterative Methods for Non-Linear Partial Differential Equations, C.W.I., Amsterdam, 1991
[22]
William F. Mitchell, Optimal multilevel iterative methods for adaptive grids, SIAM J. Sci. Statist. Comput., 13 (1992), 146–167
[23]
M. Ong, Hierarchical basis preconditioners for second order elliptic problems in three dimensions, CAM report, 89-31, Department of Mathematics, University of California at Los Angeles, Los Angeles, CA, 1993
[24]
Werner C. Rheinboldt, On the computation of multidimensional solution manifolds of parametrized equations, Numer. Math., 53 (1988), 165–181
[25]
R. Riedinger, M. Habar, P. Oelhafen, H. J. Guntherodt, About the Delaunay-Voronoi˘ tesselation, J. Comput. Phys., 74 (1988), 61–72
[26]
M. C. Rivara, Local modification of meshes for adaptive and/or multigrid finite-element methods, J. Comput. Appl. Math., 36 (1991), 79–89
[27]
W. J. Schröeder, M. S. Shephard, Geometry-based fully automatic mesh generation and the Delaunay triangulation, Internat. J. Numer. Methods Engrg., 26 (1988), 2503–2515
[28]
Mark S. Shephard, Marcel K. Georges, Reliability of automatic 3D mesh generation, Comput. Methods Appl. Mech. Engrg., 101 (1992), 443–462
[29]
E. Sperner, Neuer Beweis für die Invariant der Dimensionszahl and des Gebietes, Abh. Math. Sem. Univ. Hamburg 6
[30]
Michael J. Todd, The computation of fixed points and applications, Springer-Verlag, Berlin, 1976vii+129, Lecture Notes in Economics and Mathematical Systems 124

Cited By

View all
  • (2024)Concurrent Binary Trees for Large-Scale Game ComponentsProceedings of the ACM on Computer Graphics and Interactive Techniques10.1145/36753717:3(1-18)Online publication date: 9-Aug-2024
  • (2024)Adaptive grid generation for discretizing implicit complexesACM Transactions on Graphics10.1145/365821543:4(1-17)Online publication date: 19-Jul-2024
  • (2024)Finite number of similarity classes in Longest Edge Bisection of nearly equilateral tetrahedraApplied Mathematics and Computation10.1016/j.amc.2024.128631472:COnline publication date: 1-Jul-2024
  • Show More Cited By

Index Terms

  1. Local Bisection Refinement for N-Simplicial Grids Generated by Reflection
          Index terms have been assigned to the content through auto-classification.

          Recommendations

          Comments

          Please enable JavaScript to view thecomments powered by Disqus.

          Information & Contributors

          Information

          Published In

          cover image SIAM Journal on Scientific Computing
          SIAM Journal on Scientific Computing  Volume 16, Issue 1
          Jan 1995
          256 pages

          Publisher

          Society for Industrial and Applied Mathematics

          United States

          Publication History

          Published: 01 January 1995

          Author Tag

          1. 65M50

          Author Tags

          1. grid generation
          2. grid refinement

          Qualifiers

          • Research-article

          Contributors

          Other Metrics

          Bibliometrics & Citations

          Bibliometrics

          Article Metrics

          • Downloads (Last 12 months)0
          • Downloads (Last 6 weeks)0
          Reflects downloads up to 21 Nov 2024

          Other Metrics

          Citations

          Cited By

          View all
          • (2024)Concurrent Binary Trees for Large-Scale Game ComponentsProceedings of the ACM on Computer Graphics and Interactive Techniques10.1145/36753717:3(1-18)Online publication date: 9-Aug-2024
          • (2024)Adaptive grid generation for discretizing implicit complexesACM Transactions on Graphics10.1145/365821543:4(1-17)Online publication date: 19-Jul-2024
          • (2024)Finite number of similarity classes in Longest Edge Bisection of nearly equilateral tetrahedraApplied Mathematics and Computation10.1016/j.amc.2024.128631472:COnline publication date: 1-Jul-2024
          • (2023)Conformal Marked Bisection for Local Refinement of n-Dimensional Unstructured Simplicial MeshesComputer-Aided Design10.1016/j.cad.2022.103419154:COnline publication date: 1-Jan-2023
          • (2023)A three-step defect-correction stabilized algorithm for incompressible flows with non-homogeneous Dirichlet boundary conditionsAdvances in Computational Mathematics10.1007/s10444-023-10101-850:1Online publication date: 27-Dec-2023
          • (2022)Local coarsening of simplicial finite element meshes generated by bisectionsBIT10.1007/s10543-012-0378-052:3(559-569)Online publication date: 11-Mar-2022
          • (2022)Stable multilevel splittings of boundary edge element spacesBIT10.1007/s10543-012-0369-152:3(661-685)Online publication date: 11-Mar-2022
          • (2020)Concurrent Binary Trees (with application to longest edge bisection)Proceedings of the ACM on Computer Graphics and Interactive Techniques10.1145/34061863:2(1-20)Online publication date: 26-Aug-2020
          • (2018)Quasi-optimal convergence rate for an adaptive hybridizable $$C^0$$C0 discontinuous Galerkin method for Kirchhoff platesNumerische Mathematik10.1007/s00211-018-0953-7139:4(795-829)Online publication date: 1-Aug-2018
          • (2017)Distributed Newest Vertex BisectionJournal of Parallel and Distributed Computing10.1016/j.jpdc.2016.12.003104:C(1-11)Online publication date: 1-Jun-2017
          • Show More Cited By

          View Options

          View options

          Login options

          Media

          Figures

          Other

          Tables

          Share

          Share

          Share this Publication link

          Share on social media