The 4-triangles longest-side partition of triangles and linear refinement algorithms

Rivara, María-Cecilia; Iribarren, Gabriel

doi:10.1090/S0025-5718-96-00772-7

The 4-triangles longest-side partition of triangles and linear refinement algorithms
HTML articles powered by AMS MathViewer

by María-Cecilia Rivara and Gabriel Iribarren PDF

Math. Comp. 65 (1996), 1485-1502 Request permission

Abstract:

In this paper we study geometrical properties of the iterative 4-triangles longest-side partition of triangles (and of a 3-triangles partition), as well as practical algorithms based on these partitions, used both directly for the triangulation refinement problem, and as a basis for point insertion strategies in Delaunay refinement algorithms. The 4-triangles partition is obtained by joining the midpoint of the longest side with the opposite vertex and the midpoints of the two remaining sides. By means of simple geometrical arguments we show that the iterative partition of obtuse triangles systematically improves the triangles (while they remain obtuse) in the following sense: the sequence of smallest angles monotonically increases while the sequence of largest angles monotonically decreases in an amount (at least) equal to the smallest angle of each iteration. This allows us to improve the known bound on the smallest angle (without making use of previous results), and to obtain a better a priori bound on the number of similarly distinct triangles, as a function of the geometry of the initial triangle. Numerical evidence, showing that the practical behavior of the 4-triangles partition is in complete agreement with this theory, is included. A 4-triangles refinement algorithm is also discussed and illustrated. Furthermore, we show that the time cost of the algorithm is linear independently of the size of the triangulation.

References

I. Babuška, O. C. Zienkiewicz, J. Gago, and E. R. de A. Oliveira (eds.), Accuracy estimates and adaptive refinements in finite element computations, Wiley Series in Numerical Methods in Engineering, John Wiley & Sons, Ltd., Chichester, 1986. Lectures presented at the international conference held in Lisbon, June 1984; A Wiley-Interscience Publication. MR 879442
S. W. Bova and G. F. Carey, Mesh generation/refinement using fractal concepts and iterated function systems, Internat. J. Numer. Methods Engrg. 33 (1992), no. 2, 287–305. MR 1144653, DOI 10.1002/nme.1620330205
P. Dierckx, S. Van Leemput, and T. Vermeire, Algorithms for surface fitting using Powell-Sabin splines, IMA J. Numer. Anal. 12 (1992), no. 2, 271–299. MR 1164585, DOI 10.1093/imanum/12.2.271
Wolfgang Hackbusch, Multigrid methods and applications, Springer Series in Computational Mathematics, vol. 4, Springer-Verlag, Berlin, 1985. MR 814495, DOI 10.1007/978-3-662-02427-0
H. Kim, S. Hong, K. Choi, H. Jung and S. Hahn, A three dimensional adaptive finite element method for magnetostatic problems, IEEE Trans. Magnetics, 27(1991), 4081-4084.
L. Freitag, M. Jones and P. Plassmann, New techniques for parallel simulation of high-temperature superconductors, Argonne National Laboratory 1994 Preprint MCS-P44-0594.
S.N. Muthukrishnan, P.S. Shiakolas, R. V. Nambiar and K.L. Lawrence, A simple algorithm for the adaptive refinement of three dimensional finite element tetrahedral meshes, to appear AIAA Journal.
R.V. Nambiar, R.S. Valera, K.L. Lawrence, R. B. Morgan and D. Amil, An algorithm for adaptive refinement of triangular meshes, Internat. J. Numer. Meth. Engrg. 36 (1993), 499-509.
Joseph O’Rourke, Computational geometry column $23$, Internat. J. Comput. Geom. Appl. 4 (1994), no. 2, 239–242. MR 1288662, DOI 10.1142/S0218195994000148
J. Penman and M.D. Grieve, Self-adaptive mesh generation technique for the finite element method, IEE Proceedings, 134(1987), 634-650.
María-Cecilia Rivara, Mesh refinement processes based on the generalized bisection of simplices, SIAM J. Numer. Anal. 21 (1984), no. 3, 604–613. MR 744176, DOI 10.1137/0721042
M.-Cecilia Rivara, Algorithms for refining triangular grids suitable for adaptive and multigrid techniques, Internat. J. Numer. Methods Engrg. 20 (1984), no. 4, 745–756. MR 739618, DOI 10.1002/nme.1620200412
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
—, Adaptive finite element refinement and fully irregular and conforming triangulations, In Accuracy Estimates and Adaptive Refinements in Finite Element Computations, I. Babu$\breve {s}$ka, O.C. Zienkiewicz, J. Gago and E.R. de A. Oliveira (eds.), John Wiley & Sons, Chichester (1986), pp. 359-370.
—, A grid generator based on 4-triangles conforming mesh refinement algorithms, Internat. J. Numer. Meth. Engrg., 24 (1987), 1343-1354.
María-Cecilia Rivara, Selective refinement/derefinement algorithms for sequences of nested triangulations, Internat. J. Numer. Methods Engrg. 28 (1989), no. 12, 2889–2906. MR 1030410, DOI 10.1002/nme.1620281212
—, A discussion on the triangulation refinement problem, Proceedings of the Fifth Canadian Conference on Computational Geometry, University of Waterloo (1993), pp. 42-47.
M.-C. Rivara and C. Levin, A $3D$ refinement algorithm for adaptive and multigrid techniques, Comm. Appl. Numer. Methods, 8 (1992), 281-290.
M.-C. Rivara and M. Venere, Cost analysis of the longest-side (triangle bisection) refinement algorithms for triangulations (1994), to appear Engineering with Computers.
Ivo G. Rosenberg and Frank Stenger, A lower bound on the angles of triangles constructed by bisecting the longest side, Math. Comp. 29 (1975), 390–395. MR 375068, DOI 10.1090/S0025-5718-1975-0375068-5
Martin Stynes, On faster convergence of the bisection method for all triangles, Math. Comp. 35 (1980), no. 152, 1195–1201. MR 583497, DOI 10.1090/S0025-5718-1980-0583497-1
R. Williams, Adaptive parallel meshes with complex geometry, In Numerical Grid Generation in Computational Fluid Dynamics and Related Fields (A.S.Arcilla, J.Hauser, P.R.Eiseman, J.F.Thompson, eds.), Elsevier Science Publishers B.V. (North-Holland) (1991).