On generalized bisection of 𝑛-simplices

Horst, Reiner

doi:10.1090/S0025-5718-97-00809-0

On generalized bisection of $n$-simplices
HTML articles powered by AMS MathViewer

by Reiner Horst PDF

Math. Comp. 66 (1997), 691-698 Request permission

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

Andrew Adler, On the bisection method for triangles, Math. Comp. 40 (1983), no. 162, 571–574. MR 689473, DOI 10.1090/S0025-5718-1983-0689473-5
Eugene L. Allgower and Kurt Georg, Numerical continuation methods, Springer Series in Computational Mathematics, vol. 13, Springer-Verlag, Berlin, 1990. An introduction. MR 1059455, DOI 10.1007/978-3-642-61257-2
Eugene L. Allgower and Kurt Georg, Continuation and path following, Acta numerica, 1993, Acta Numer., Cambridge Univ. Press, Cambridge, 1993, pp. 1–64. MR 1224680, DOI 10.1017/s0962492900002336
B. Curtis Eaves, A course in triangulations for solving equations with deformations, Lecture Notes in Economics and Mathematical Systems, vol. 234, Springer-Verlag, Berlin, 1984. MR 871269, DOI 10.1007/978-3-642-46516-1
A. Eiger, K. Sikorski, and F. Stenger, A bisection method for systems of nonlinear equations, ACM Trans. Math. Software 10 (1984), no. 4, 367–377. MR 792001, DOI 10.1145/2701.2705
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.
R. Horst, An algorithm for nonconvex programming problems, Math. Programming 10 (1976), 312–321.
R. Horst and P.M. Pardalos (editors), Handbook of Global Optimization, Kluwer, Dordrecht, Boston, 1995.
Reiner Horst and Hoang Tuy, Global optimization, 2nd ed., Springer-Verlag, Berlin, 1993. Deterministic approaches. MR 1274246, DOI 10.1007/978-3-662-02947-3
Baker Kearfott, A proof of convergence and an error bound for the method of bisection in $\textbf {R}^{n}$, Math. Comp. 32 (1978), no. 144, 1147–1153. MR 494897, DOI 10.1090/S0025-5718-1978-0494897-3
Anwei Liu and Barry Joe, On the shape of tetrahedra from bisection, Math. Comp. 63 (1994), no. 207, 141–154. MR 1240660, DOI 10.1090/S0025-5718-1994-1240660-4
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
M.–C. Rivara, A grid generator based on 4–triangles conforming mesh–refinement algorithms, Internat. J. Numer. Methods Engrg. 24 (1987), 1343–1354.
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
Krzysztof Sikorski, A three-dimensional analogue to the method of bisections for solving nonlinear equations, Math. Comp. 33 (1979), no. 146, 722–738. MR 521286, DOI 10.1090/S0025-5718-1979-0521286-6
Frank Stenger, Computing the topological degree of a mapping in $\textbf {R}^{n}$, Numer. Math. 25 (1975/76), no. 1, 23–38. MR 394639, DOI 10.1007/BF01419526
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