Properties of triangulations obtained by the longest-edge bisection

Francisco Perdomo ; Ángel Plaza

Open Mathematics, Tome 12 (2014), p. 1796-1810 / Harvested from The Polish Digital Mathematics Library

Résumé

The Longest-Edge (LE) bisection of a triangle is obtained by joining the midpoint of its longest edge with the opposite vertex. Here two properties of the longest-edge bisection scheme for triangles are proved. For any triangle, the number of distinct triangles (up to similarity) generated by longest-edge bisection is finite. In addition, if LE-bisection is iteratively applied to an initial triangle, then minimum angle of the resulting triangles is greater or equal than a half of the minimum angle of the initial angle. The novelty of the proofs is the use of an hyperbolic metric in a shape space for triangles.

Détail

Publié le : 2014-01-01

Zbl 1315.51018

EUDML-ID : urn:eudml:doc:268957

Bibliographie

[1] Adler A., On the bisection method for triangles, Math. Comp., 1983, 40, 571–574 http://dx.doi.org/10.1090/S0025-5718-1983-0689473-5 | Zbl 0523.65033

[2] Babuška I., Aziz A. K., On the angle condition in the finite element method. SIAM J. Numer. Anal. 1976, 13, 214–226 http://dx.doi.org/10.1137/0713021 | Zbl 0324.65046

[3] Bern M., Eppstein D., Optimal Möbius transformations for information visualization and meshing, Lecture Notes in Comp. Sci., 2001, 2125, 14–25 http://dx.doi.org/10.1007/3-540-44634-6_3 | Zbl 0997.68536

[4] Bookstein F.L., Morphometric Tools for Landmark Data: Geometry and Biology, Cambridge University Press, 1991 | Zbl 0770.92001

[5] Brandts J., Korotov S., KříŽek M., On the equivalence of regularity criteria for triangular and tetrahedral finite element partitions, Comput. & Math. Appl., 2008, 55, 2227–2233 http://dx.doi.org/10.1016/j.camwa.2007.11.010 | Zbl 1142.65443

[6] Ciarlet P. G., The Finite Element Method for Elliptic Problems. North-Holland, Amsterdam, 1978. | Zbl 0383.65058

[7] Dryden I.L., Mardia K.V., Statistical Shape Analysis, Wiley, 1998 | Zbl 0901.62072

[8] Eppstein D., Manhattan orbifolds, Topology and its Applications, 2009, 157(2), 494–507 http://dx.doi.org/10.1016/j.topol.2009.10.008 | Zbl 1200.68169

[9] Eppstein D., Succinct greedy geometric routing using hyperbolic geometry, IEEE Transactions on Computing, 2011, 60(11), 1571–1580 http://dx.doi.org/10.1109/TC.2010.257

[10] Gutiérrez C., Gutiérrez F., Rivara M.-C., Complexity of bisection method, Theor. Comp. Sci., 2007, 382, 131–138 http://dx.doi.org/10.1016/j.tcs.2007.03.004 | Zbl 1127.68108

[11] Hannukainen A., Korotov S., Křížek M., On global and local mesh refinements by a generalized conforming bisection algorithm, J. Comput. Appl. Math., 2010, 235, 419–436 http://dx.doi.org/10.1016/j.cam.2010.05.046 | Zbl 1207.65145

[12] Iversen B., Hyperbolic Geometry, Cambridge University Press, 1992 http://dx.doi.org/10.1017/CBO9780511569333

[13] Korotov S., Křížek M., Kropác A., Strong regularity of a family of face-to-face partitions generated by the longestedge bisection algorithm, Comput. Math. and Math. Phys., 2008, 49, 1687–1698 http://dx.doi.org/10.1134/S0965542508090170

[14] Křížek M., On semiregular families of triangulations and linear interpolation, Appl. Math., 1991, 36, 223–232 | Zbl 0728.41003

[15] Márquez A., Moreno-González A., Plaza A., Suárez J. P., The seven-triangle longest-side partition of triangles and mesh quality improvement, Finite Elem. Anal. Des., 2008, 44, 748–758 http://dx.doi.org/10.1016/j.finel.2008.04.007

[16] Padrón M. A., Suárez J. P., Plaza A., A comparative study between some bisection based partitions in 3D, Appl. Num. Math., 2005, 55, 357–367 http://dx.doi.org/10.1016/j.apnum.2005.04.035 | Zbl 1087.65615

[17] Perdomo F., Plaza A., A new proof of the degeneracy property of the longest-edge n-section refinement scheme for triangular meshes, Appl. Math. & Compt., 2012, 219, 2342–2344 http://dx.doi.org/10.1016/j.amc.2012.08.029 | Zbl 1291.65353

[18] Perdomo F., Plaza A., Proving the non-degeneracy of the longest-edge trisection by a space of triangular shapes with hyperbolic metric, Appl. Math. & Compt., 2013, 221, 424–432 http://dx.doi.org/10.1016/j.amc.2013.06.075 | Zbl 1332.51009

[19] Perdomo F., Dynamics of the longest-edge partitions in a triangle space endowed with an hyperbolic metric, Ph.D. Thesis (in Spanish), Las Palmas de Gran Canaria, 2013

[20] Plaza A., Padrón M. A., Suárez J. P., Non-degeneracy study of the 8-tetrahedra longest-edge partition, Appl. Num. Math., 2005, 55, 458–472 http://dx.doi.org/10.1016/j.apnum.2004.12.003 | Zbl 1086.65507

[21] Plaza A., Suárez J. P., Padrón M. A, Falcón S., Amieiro D., Mesh quality improvement and other properties in the four-triangles longest-edge partition. Comp. Aid. Geom. Des., 2004, 21, 353–369 http://dx.doi.org/10.1016/j.cagd.2004.01.001 | Zbl 1069.65530

[22] Plaza A., Suárez J. P., Carey G. F., A geometric diagram and hybrid scheme for triangle subdivision, Comp. Aid. Geom. Des., 2007, 24, 19–27 http://dx.doi.org/10.1016/j.cagd.2006.10.002 | Zbl 1171.65349

[23] Rivara M.-C., Mesh refinement processes based on the generalized bisection of simplices, SIAM J. Num. Anal., 1984, 21, 604–613 http://dx.doi.org/10.1137/0721042 | Zbl 0574.65133

[24] Rosenberg I. G., Stenger F., A lower bound on the angles of triangles constructed by bisecting the longest side, Math. Comp., 1975, 29, 390–395 http://dx.doi.org/10.1090/S0025-5718-1975-0375068-5 | Zbl 0302.65085

[25] Stahl S., The Poincaré Half-Plane, Jones & Bartlett Learning, 1993

[26] Stynes M., On faster convergence of the bisection method for certain triangles, Math. Comp., 1979, 33, 717–721 http://dx.doi.org/10.1090/S0025-5718-1979-0521285-4 | Zbl 0405.65010

[27] Stynes M., On faster convergence of the bisection method for all triangles, Math. Comp., 1980, 35, 1195–1201 http://dx.doi.org/10.1090/S0025-5718-1980-0583497-1 | Zbl 0463.65005

[28] Toth G., Glimpses of Algebra and Geometry, Springer, 2002 | Zbl 1027.00002