Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



On generalized bisection of $n$-simplices

Author: Reiner Horst
Journal: Math. Comp. 66 (1997), 691-698
MSC (1991): Primary 51M20, 90Bxx; Secondary 52B10, 65M50, 65N50, 90Cxx
MathSciNet review: 1388889
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: A generalized procedure of bisection of $n$-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 $n$. For $n = 2$ and $3$, the sequence of worst case diameters is provided until it is halved.

References [Enhancements On Off] (What's this?)

  • 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 $\mathbb {R} ^n$ 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 $\mathbb {R} ^n$, 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

Similar Articles

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

Received by editor(s): May 10, 1995
Received by editor(s) in revised form: March 13, 1996
Article copyright: © Copyright 1997 American Mathematical Society

American Mathematical Society