Computational Geometry, Triangulation Papers and Software 1992-1994
"Linear-size nonobtuse triangulation of polygons" is a circle packing based algorithm for generating a triangulation consisting of all right triangles. Matlab R2010a Implementation (gzipped tar file)
"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. Matlab R2010a Implementation (gzipped tar file) You will need to get the "Linear-size nonobtuse…" implementation as well. Some filenames may be the same so keep the directories separate: instructions are in the file README2.
"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. 2d Implementation: get both the C++ source and the documentation + Matlab GUI. 2d/3d/nd: QMG implementations Steve Vavasis.
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, Scott A. Mitchell, Applied Math Cornell Ph.D. Thesis. On Cornell CS Tech Report TR93-1327 (1993) , and Cornell CS Tech Reports page.
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 in Ph.D. Thesis, Cornell CS TR 92-1327 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 in Ph.D. Thesis, Cornell CS TR 92-1327.
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.