Delaunay Mesh Generation
CRC Press, Boca Raton, Florida, December 2012. xii+375 pages.
Tamal Krishna Dey
Jonathan Richard Shewchuk
Hong Kong University of Science and Technology
The Ohio State University
University of California at Berkeley
Buy it from
Amazon, or from
Please send comments, questions, and
all three authors at
Our book is a thorough guide to Delaunay refinement algorithms that are
mathematically guaranteed to generate meshes with high quality, including
triangular meshes in the plane, tetrahedral volume meshes, and triangular
surface meshes embedded in three dimensions.
It is also the most complete guide available to
Delaunay triangulations and algorithms for constructing them.
We have designed the book for two audiences: researchers, especially graduate
students, and engineers who design and program mesh generation software.
Exercises are included; so is implementation advice.
Delaunay refinement algorithms for mesh generation
construct meshes of triangles or tetrahedra (“elements”)
that are suitable for applications like interpolation, rendering,
terrain databases, geographic information systems,
and most demandingly, the solution of partial differential equations
by the finite element method.
Delaunay refinement algorithms operate by maintaining a Delaunay or
constrained Delaunay triangulation which is refined by inserting
additional vertices until the mesh meets constraints
on element quality and size.
These algorithms offer theoretical bounds on element quality, edge lengths, and
spatial grading of element sizes;
topological and geometric fidelity to complicated domains,
including curved domains with internal boundaries;
and truly satisfying performance in practice.
The first third of the book lays out the mathematical underpinnings of
Delaunay triangulations and the most practical algorithms
for constructing them.
The second third of the book describes Delaunay refinement algorithms
for domains expressed as piecewise linear complexes,
which model polygons and polyhedra but also support internal boundaries.
The final third of the book describes Delaunay refinement algorithms
for curved domains—specifically, smooth surfaces,
volumes bounded by smooth surfaces, and piecewise smooth domains
that have curved ridges and patches and are
represented by piecewise smooth complexes.
The book has fifteen chapters, summarized below.
Check out free samples of
of Contents and Preface (PDF, 198k, 13 pages),
1 (PDF, 708k, 30 pages),
2 (PDF, 286k, 24 pages),
9 (PDF, 472k, 17 pages), and
13 (PDF, 455k, 29 pages).
Meshes and the goals of mesh generation; a brief history of mesh generation;
simplices, complexes, and polyhedra; metric space topology;
how to measure and judge elements.
Two-dimensional Delaunay triangulations.
Triangulations and Delaunay triangulations of point sets;
the parabolic lifting map; the Delaunay Lemma; the flip algorithm;
the optimality and uniqueness of the Delaunay triangulation;
weighted Delaunay triangulations;
triangulations of polygons and piecewise linear complexes;
constrained Delaunay triangulations.
3. Algorithms for constructing Delaunay triangulations.
Geometric predicates; data structures;
inserting or deleting a vertex in
a Delaunay triangulation or a constrained Delaunay triangulation;
incremental vertex insertion algorithms and their analysis;
inserting a segment into a constrained Delaunay triangulation;
the gift-wrapping algorithm.
4. Three-dimensional Delaunay triangulations.
Triangulations and Delaunay triangulations in higher dimensions;
the optimality of higher-dimensional Delaunay triangulations;
bistellar flips and the flip algorithm;
three-dimensional constrained Delaunay triangulations; the CDT Theorem.
5. Algorithms for constructing Delaunay triangulations in R3.
inserting a vertex or a polygon into a constrained Delaunay triangulation;
incremental vertex insertion algorithms in three dimensions and their analysis;
biased randomized insertion orders;
gift-wrapping in three dimensions.
6. Delaunay refinement in the plane.
Delaunay refinement algorithms;
Ruppert's algorithm for triangular mesh generation; implementation;
guarantees of termination, good quality, size optimality, and optimal grading;
domains with small angles; constrained Delaunay refinement.
7. Voronoi diagrams and weighted complexes.
weighted Voronoi diagrams and weighted Delaunay triangulations;
8. Tetrahedral meshing of PLCs.
Tetrahedral Delaunay refinement; implementation;
guarantees of termination, good quality, and good grading;
refining slivers away; constrained Delaunay tetrahedral refinement.
Weighted Delaunay refinement for PLCs with small angles.
Principles of weighted Delaunay refinement; protecting vertices and segments;
a weighted Delaunay refinement algorithm;
guarantees of termination and good grading.
10. Sliver exudation.
Principles of sliver exudation; implementation; the Sliver Theorem.
11. Refinement for sliver exudation.
a weighted Delaunay refinement algorithm for sliver exudation;
guarantees of domain conformity, termination, good quality, and good grading;
revisiting the Sliver Theorem.
12. Smooth surfaces and point samples.
Topological spaces; maps, homeomorphisms, and isotopies;
manifolds; smooth manifolds;
the medial axis and the local feature size; ε-samples of surfaces;
approximation theory for well-sampled surfaces.
Restricted Delaunay triangulations of surface samples.
Restricted Voronoi diagrams and restricted Delaunay triangulations;
the Topological Ball Theorem; distances and angles in ε-samples;
properties of restricted Voronoi faces;
homeomorphism, isotopy, and geometric fidelity of
restricted Delaunay triangulations of well-sampled surfaces.
14. Meshing smooth surfaces and volumes.
Triangular Delaunay surface meshing with a known local feature size;
topology-driven surface meshing; practical surface meshing;
enforcing quality and smoothness; remeshing polyhedral surfaces;
tetrahedral meshing of volumes bounded by smooth surfaces.
15. Meshing piecewise smooth complexes.
Piecewise smooth complexes and their triangulations;
protecting vertices and ridges;
a Delaunay refinement algorithm for meshing PSCs; the PSC Lemma;
guarantees of termination, good quality, and homeomorphism;
enforcing quality; volume meshing.