On generalized bisection of -simplices

Author:
Reiner Horst

Journal:
Math. Comp. **66** (1997), 691-698

MSC (1991):
Primary 51M20, 90Bxx; Secondary 52B10, 65M50, 65N50, 90Cxx

DOI:
https://doi.org/10.1090/S0025-5718-97-00809-0

MathSciNet review:
1388889

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: A generalized procedure of bisection of -simplices is introduced, where the bisection point can be an (almost) arbitrary point at one of the longest edges. It is shown that nested sequences of simplices generated by successive generalized bisection converge to a singleton, and an exact bound of the convergence speed in terms of diameter reduction is given. For regular simplices, which mark the worst case, the edge lengths of each worst and best simplex generated by successive bisection are given up to depth . For and , the sequence of worst case diameters is provided until it is halved.

**1.**A. Adler,*On the bisection method for triangles*, Math. Comp.**40**(1983), 571-574. MR**84d:51028****2.**E.L. Allgower and K. Georg,*Numerical Continuation Methods: An Introduction*, Springer Series in Computational Mathematics,**13**, Berlin, Heidelberg, New York, 1990. MR**92a:65165****3.**E.L. Allgower and K. Georg,*Continuation and Path Following*, Acta Numerica**1**(1993), 1-64. MR**94k:65076****4.**B.C. Eaves,*A course in triangulations for solving equations with deformations*, Lecture Notes in Economics and Mathematical Systems**234**, Springer-Verlag, Berlin, Heidelberg, New York 1984. MR**87m:90111****5.**A. Eiger, K. Sikorski, F. Stenger,*A bisection method for systems of nonlinear equations*, ACM Trans. Math. Software**10**(1984), 367-377. MR**86g:65102****6.**R. Horst,*A new branch and bound approach for concave minimization problems*, Lecture Notes in Computer Science**41**, 330-337, Springer-Verlag, Berlin, Heidelberg, New York, 1975.**7.**R. Horst,*An algorithm for nonconvex programming problems*, Math. Programming**10**(1976), 312-321.**8.**R. Horst and P.M. Pardalos (editors),*Handbook of Global Optimization*, Kluwer, Dordrecht, Boston, 1995. CMP**96:09****9.**R. Horst and H. Tuy,*Global Optimization*, 2nd revised edition, Springer-Verlag, Berlin, Heidelberg, New York, 1993. MR**94m:90004****10.**B. Kearfott,*A proof of convergence and an error bound for the method of bisection in*Math. Comp.**32**(1978), 1147-1153. MR**58:13677****11.**A. Liu and B. Joe,*On the shape of tetrahedra from bisection*, Math. Comp.**63**(1994), 141-154. MR**94j:65113****12.**M.-C. Rivara,*Mesh refinement processes based on the generalized bisection of simplices*, SIAM J. Numer. Anal.**21**(1984), 604-613. MR**85i:65159****13.**M.-C. Rivara,*Algorithms for refining triangular grids suitable for adaptive and multigrid techniques*, Internat. J. Numer. Methods Engrg.**20**(1984), 745-756. MR**85h:65258****14.**M.-C. Rivara,*A grid generator based on 4-triangles conforming mesh-refinement algorithms*, Internat. J. Numer. Methods Engrg.**24**(1987), 1343-1354.**15.**I.G. Rosenberg and F. Stenger,*A lower bound on the angles of triangles constructed bisecting the longest side*, Math. Comp.**29**(1975), 390-395. MR**51:11264****16.**K. Sikorski,*A three dimensional analogue to the method of bisections for solving nonlinear equations*, Math. Comp.**33**(1979), 722-738. MR**80i:65058****17.**F. Stenger,*Computing the topological degree of a mapping in*, Numer. Math.**25**(1976), 23-38. MR**52:15440****18.**M. Stynes,*On faster convergence of the bisection method for all triangles*, Math. Comp.**35**(1980), 1195-1201. MR**81j:51023**

Retrieve articles in *Mathematics of Computation of the American Mathematical Society*
with MSC (1991):
51M20,
90Bxx,
52B10,
65M50,
65N50,
90Cxx

Retrieve articles in all journals with MSC (1991): 51M20, 90Bxx, 52B10, 65M50, 65N50, 90Cxx

Additional Information

**Reiner Horst**

Affiliation:
Department of Mathematics, University of Trier, Trier 54286, Germany

Email:
horst@uni-trier.de

DOI:
https://doi.org/10.1090/S0025-5718-97-00809-0

Received by editor(s):
May 10, 1995

Received by editor(s) in revised form:
March 13, 1996

Article copyright:
© Copyright 1997
American Mathematical Society