"Finding a covering triangulation whose maximum angle is provably small" considers the restriction that no boundary Steiner-vertices are allowed. This algorithm buffers the input edges with circular arcs, then uses the above algorithm as a subroutine.

"Quality mesh generation in three dimensions" describes a three dimensional octree based tetrahedralization algorithm for no small (solid or dihedral) angles. Probably one of the more novel features are that octree boxes are duplicated for each connected component of their intersection with the input. This avoids the small box-size "bleed-through" effect.

The following files are all pdf:
"Refining a triangulation of a planar straight-line graph to eliminate large angles" gives a practical and almost optimal way to do just that.
"Approximating the maxmin angle covering triangulation" considers bounding the smallest angle when no boundary vertices are allowed.
"Cardinality bounds for triangulations with bounded minimum angle" simplifies the main proof of the previous paper and applies it to give a lower bound for the number of no-small-angle triangles necessary to triangulate a given input, and provides you with a simple way to show that an algorithm you come up with comes close to this bound. (Note: there is a mistake in the last theorem of the paper. It should read "$k_2 = k_1^{-2} bigo( 1 / alpha )$" rather than "$k_2 = k_1^2 bigo( 1 / alpha )$." Thanks to Steven Elliot Pav [spav@andrew.cmu.edu] for pointing this out.)
"Edge insertion for optimal triangulations" extends the edge insertion algorithm to the generation of optimal (non-Steiner) triangulations for several metrics.

Bibliography

Mesh Generation With Provable Quality Bounds, S. A. Mitchell, Applied Math Cornell PhD Thesis, Cornell CS Tech Report TR93-1327 (1993).

Cardinality Bounds for Triangulations with Bounded Minimum Angle, S. A. Mitchell, Sixth Canadian Conference on Computational Geometry (1994), 326-331.

Linear-Size Nonobtuse Triangulation of Polygons, M. Bern, S. A. Mitchell and J. Ruppert, Proc. 10th Annual Symposium on Computational Geometry (1994), 121-130.

Refining a Triangulation of a Planar Straight-Line Graph to Eliminate Large Angles, S. A. Mitchell, Thirty-fourth Annual Symposium on Foundations of Computer Science (FOCS '93), 583-591.

Finding a Covering Triangulation Whose Maximum Angle is Provably Small, S. A. Mitchell, Int. J. Comput. Geometry Appl., pp. 5-20, 1997. And Seventeenth Annual (Australasian) Computer Science Conference, pp. 55-64, 1994. And the 1993 ARO/MSI Stony Brook Workshop on Computational Geometry.

Approximating the MaxMin-Angle Covering Triangulation, S. A. Mitchell, Proc. Fifth Canadian Conference on Computational Geometry (1993), 36-41. Also Cornell CS TR 92-1327 (thesis) and COMPUTATIONAL GEOMETRY: Theory and Applications 7 (1997) 93-111.

Quality Mesh Generation in Three Dimensions, S. A. Mitchell and S. A. Vavasis, Proc. 8th Annual Symposium on Computational Geometry (1992), 212-221. Also presented a two-dimensional implementation at the 1991 SUNY Stony Brook Workshop on Computational Geometry. Also Cornell CTC92TR104 9/92 and Cornell CS TR 92-1327 (thesis).

Edge-Insertion for Optimal Triangulations, M. Bern, H. Edelsbrunner, D. Eppstein, S. A. Mitchell, and T. S. Tan, Proc. Latin American Theoretical Informatics 1992, 46-60. Also Discrete & Computational Geometry 10:47-65 (1993) Springer-Verlag New York Inc.

An Aspect Ratio Bound for Triangulating a d-Grid Cut by a Hyperplace, S. A. Mitchell and S. A. Vavasis, Proc. 12th Annual Symposium on Computational Geometry, (1996) 48-57.

Quality Mesh Generation in Higher Dimensions, Scott A. Mitchell and Stephen A. Vavasis, SIAM Journal on Computing Volume 29, Number 4, pp. 1334-1370. 1999.

Links