Delaunay Mesh Generation


Siu-Wing Cheng
Tamal Krishna Dey
Jonathan Richard Shewchuk
Hong Kong University of Science and Technology
The Ohio State University
University of California at Berkeley
-------------------------------------------------------------------
-------------------------------------------------------------------
-------------------------------------------------------------------
CRC Press, Boca Raton, Florida, December 2012. xii+375 pages.
Buy it from Taylor & Francis, from Amazon, or from Barnes & Noble.
Please send comments, questions, and errata to 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 the Table of Contents and Preface (PDF, 198k, 13 pages), Chapter 1 (PDF, 708k, 30 pages), Chapter 2 (PDF, 286k, 24 pages), Chapter 9 (PDF, 472k, 17 pages), and Chapter 13 (PDF, 455k, 29 pages).

Erratum

Let us know if you find errors.