Results on triangulation and high quality mesh generation
James Martin Ruppert · 1992
We present several results on the triangulation problem in 2D and 3D. Given a polygonal or polyhedral object, a triangulation is a decomposition of the object into a collection of non-overlapping triangles or tetrahedra. Since the resulting pieces form a mesh of the object, the process of triangulation is also called mesh generation. Two main types of triangulations are distinguished by whether they contain Steiner points: vertices of the triangulation that are not vertices of the input. Non-Steiner triangulation has been well studied in 2D and is possible for every polygon. However, not every polyhedron in 3D admits a non-Steiner triangulation. Here we show that determining whether a given polyhedron can be triangulated without the use of Steiner points is an NP-complete problem, and hence likely to be computationally intractable. Another consideration is the shape of the pieces. For applications such as the finite element method, excessively skinny triangles or tetrahedra may hurt the convergence or stability of numerical computations. The quality mesh generation problem requires the triangulation to satisfy some shape bound. (In general, this will necessitate the use of Steiner points.) For instance, one may want all pieces' aspect ratios to be less than some global maximum, where the aspect ratio of an object is its length divided by its width. We present a 2D algorithm for triangulating polygons such that all triangles have a bounded aspect ratio. The algorithm is based on successive refinement of a Delaunay triangulation, and produces a mesh that is size-optimal, meaning that the number of triangles is within a constant factor of the minimum possible for the given input and aspect ratio bound. We also describe a 3D version of the Delaunay refinement algorithm that has neither size nor shape guarantees, but performs well in practice. Our work makes several contributions to the study of triangulation and mesh generation. In 2D, our Delaunay refinement algorithm helps to narrow the gap between triangulation theory and practice. In 3D, we add to the theoretical understanding of triangulation and towards the ultimate goal of a practical, reliable, high-quality mesh generation algorithm.