Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

 

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


Authors: María-Cecilia Rivara and Gabriel Iribarren
Journal: Math. Comp. 65 (1996), 1485-1502
MSC (1991): Primary 65M50, 65N50, 65M60, 65N30, 51N30, 51M15; Secondary 65Y25, 68U05, 65M55
MathSciNet review: 1361811
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 65M50, 65N50, 65M60, 65N30, 51N30, 51M15, 65Y25, 68U05, 65M55

Retrieve articles in all journals with MSC (1991): 65M50, 65N50, 65M60, 65N30, 51N30, 51M15, 65Y25, 68U05, 65M55


Additional Information

María-Cecilia Rivara
Affiliation: Department of Computer Science, University of Chile, Casilla 2777, Santiago, Chile
Email: mcrivara@dcc.uchile.cl

Gabriel Iribarren
Affiliation: Department of Computer Science, University of Chile, Casilla 2777, Santiago, Chile
Email: giribar@dcc.uchile.cl

DOI: http://dx.doi.org/10.1090/S0025-5718-96-00772-7
PII: S 0025-5718(96)00772-7
Received by editor(s): September 5, 1994
Received by editor(s) in revised form: May 30, 1995
Article copyright: © Copyright 1996 American Mathematical Society