| In this thesis, the problem of planar mesh generation with quality bounds is considered. A good mesh generation algorithm should accept an arbitrary planar straight line graph and output a Delaunay Triangulation of a set of points (all the input points plus some acceptably small number of Steiner Points) which conforms to the input and has no small or large angles. Ruppert's algorithm for solving this problem is reanalyzed: it is shown that this algorithm terminates for a larger class of input than previously proven. The analysis removes a deficiency of Ruppert's original exposition and analysis: the requirement that input segments meet at nonacute angles.; An “adaptive” variant of the algorithm is introduced. This simple variant deals with small input angles adaptively, producing meshes where most triangles have no small angles, except where conformality to the input prevents this. The analysis shows that small output angles of the mesh are not much smaller than nearby small input angles, and that large angles are entirely prevented. As in Ruppert's algorithm, the output meshes are “well-graded” in the sense that the size of edges in the output is bounded by some function of the input.; Lastly, a certain measure on triangulations with bounded minimum angle is considered. This measure is similar to that analyzed by Mitchell. The new measure allows an asymptotic improvement in the optimality claims of the algorithms considered. |
