Scott A. Mitchell

Computational Geometry
Triangulation Papers and Software
1992-1994

[Sandia National Laboratories]
For more of Scott A. Mitchell's papers see also
Google Scholar Profile
Papers 2007+
Meshing papers, 1993-2002.

"Linear-size nonobtuse triangulation of polygons" is a circle packing based algorithm for generating a triangulation consisting of all right triangles.

Full Paper (pdf) 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.

Full Paper (pdf) 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.

Full Paper (pdf) 2d Implementation: get both the C++ source and the documentation + Matlab GUI.
2d/3d: QMG implementation and papers by 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.

Links

  • Computational Geometry Bibliography and citeseer are good places to look up papers.
  • Mathtools.net is a good place to look up scientific computing resources.
  • CUBIT mesh generation toolkit

  • Back to Scott A. Mitchell's home page