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.

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

Received by editor(s):
September 5, 1994

Received by editor(s) in revised form:
May 30, 1995

Article copyright:
© Copyright 1996
American Mathematical Society