Construction and Analysis of Unstructured Mesh Generation Algorithms

Given a collection of points, edges, and faces, in a bounded region in two or three dimensions, the meshing problem is to construct a triangulation which

(i) "conforms" to the input,

(ii) the triangles or tetrahedra have bounded aspect ratio, and

(iii) is as coarse as possible.

These requirements can lead to very complicated algorithms; so much so that it can be difficult to verify correctness. I will give an overview of the ideas and issues that arise when constructing algorithms to solve the meshing problem, and will indicate how the mesh generation problem touches on many areas of mathematics and computer science, such as approximation/interpolation theory, computational geometry, sphere packing, graph theory, and algorithm design.