Geometry in Action

Mesh Generation

A key step of the finite element method for numerical computation is mesh generation. One is given a domain (such as a polygon or polyhedron; more realistic versions of the problem allow curved domain boundaries) and must partition it into simple "elements" meeting in well-defined ways. There should be few elements, but some portions of the domain may need small elements so that the computation is more accurate there. All elements should be "well shaped" (which means different things in different situations, but generally involves bounds on the angles or aspect ratio of the elements). One distinguishes "structured" and "unstructured" meshes by the way the elements meet; a structured mesh is one in which the elements have the topology of a regular grid. Structured meshes are typically easier to compute with (saving a constant factor in runtime) but may require more elements or worse-shaped elements. Unstructured meshes are often computed using quadtrees, or by Delaunay triangulation of point sets; however there are quite varied approaches for selecting the points to be triangulated.

There has now been considerable theoretical work in the geometry community on these problems, complementing and building on practical work in the numerical community. There is also beginning to be a convergence of these communities, in which theoretical work is fed back in to practical mesh generation applications. Theoretically, the preferred type of mesh is the triangulation or simplicial complex, but in mesh generation practice quadrilaterals or higher dimensional cubical element shapes are preferred (both because fewer are typically needed and because they have better numerical properties). Remaining problem areas in the theory of meshing include triangulations in dimensions higher than two, meshes with cubical elements, mesh smoothing, mesh decimation and multigrid methods, and data structures for efficient implementation of meshing algorithms. There has also been some theoretical work on using geometry to partition meshes by finding small separators of their underlying graphs.

The list of pointers here is not intended to be comprehensive; see Robert Schneiders' page for more pointers. I have tried to include a mixture of research groups working on theoretical problems with commercial packages and the issues they raise.

Part of Geometry in Action, a collection of applications of computational geometry.
David Eppstein, Theory Group, ICS, UC Irvine.

Semi-automatically filtered from a common source file.