My work on mesh generation has been motivated by the finite element method for finding approximate solutions to partial differential equations. The first step of this method is to create a mesh, i.e. to divide the given problem region into simple shapes called elements (usually triangles or quadrilaterals in 2D, tetrahedra or hexahedra in 3D). A number of algorithms have been developed to automate this process, but most of them don't guarantee the quality of the resulting mesh (e.g. a triangle may cross a region boundary or there may be some flat triangles, leading to poor error bounds). I developed efficient techniques for producing meshes of guaranteed quality for problems in the plane and for curved surfaces. The triangles produced are close to equilateral in shape; all region boundaries are respected; and the user can control the element density, producing small elements in "interesting" regions and large elements elsewhere. I extended this work to produce tetrahedral meshes for threedimensional problems. The major difficulty here is to avoid producing "slivers": tetrahedra with nicely shaped faces but with nearzero volume. My new technique is based on the idea of choosing each new mesh point randomly within a small specified volume. I showed how to choose a new mesh point, in constant expected time, that is guaranteed not to form new slivers. Professional ActivitiesReviewer: Mathematical Programming, John Wiley and Sons. Lectures
