Delaunay Mesh Generation (Hardcover)

Introduction
Meshes and the goals of mesh generation
Delaunay triangulations and Delaunay refinement algorithms
A brief history of mesh generation
A personal history of working in mesh generation
Simplices, complexes, and polyhedra
Metric space topology
How to measure an element

Two-Dimensional Delaunay Triangulations
Triangulations of a planar point set
The Delaunay triangulation
The parabolic lifting map
The Delaunay Lemma
The flip algorithm
The optimality of the Delaunay triangulation
The uniqueness of the Delaunay triangulation
The weighted Delaunay triangulation
Symbolic weight perturbations
Constrained Delaunay triangulations in the plane

Algorithms for Constructing Delaunay Triangulations
The orientation and incircle predicates
A dictionary data structure for triangulations
Inserting a vertex into a Delaunay triangulation
Inserting a vertex outside a Delaunay triangulation
The running time of vertex insertion
Optimal point location by a conflict graph
The incremental insertion algorithm
Deleting a vertex from a Delaunay triangulation
Inserting or deleting a vertex in a CDT
Inserting a segment into a CDT
The gift-wrapping algorithm

Three-Dimensional Delaunay Triangulations
Triangulations of a point set in R^d
The Delaunay triangulation in R^d
The optimality of the Delaunay triangulation in R^d
Bistellar flips and the flip algorithm
Three-dimensional constrained Delaunay triangulations

Algorithms for Constructing Delaunay Triangulations in R³
A dictionary data structure for tetrahedralizations
Delaunay vertex insertion in R³
Biased randomized insertion orders
Optimal point location by a conflict graph in R³
Point location by walking
The gift-wrapping algorithm in R³
Inserting a vertex into a CDT in R³
Inserting a polygon into a CDT

Delaunay Refinement in the Plane
A generic Delaunay refinement algorithm
Ruppert’s Delaunay refinement algorithm
Implementation and running time
A proof of termination
A proof of size optimality and optimal grading
Meshing domains with small angles
Constrained Delaunay refinement

Voronoi Diagrams and Weighted Complexes
Voronoi diagrams
Weighted Voronoi and weighted Delaunay
Quarantined complexes

Tetrahedral Meshing of PLCs
A tetrahedral Delaunay refinement algorithm
Implementation and running time
A proof of termination and good grading
Refining slivers away
Constrained Delaunay tetrahedral refinement

Weighted Delaunay Refinement for PLCs with Small Angles
The ideas behind weighted Delaunay refinement
Protecting vertices and segments
The refinement stage
A proof of termination and good grading

Sliver Exudation
The main idea and the algorithm
Implementing sliver exudation
Properties of the union of weighted Delaunay triangulations
The Sliver Theorem

Refinement for Sliver Exudation
Enforcing domain conformity with uncertain vertex weights
A refinement algorithm for sliver exudation
A guarantee of domain conformity during sliver exudation
A proof of termination, good quality, and good grading
Finite triangulations and the Sliver Theorem

Smooth Surfaces and Point Samples
Topological spaces
Maps, homeomorphisms, and isotopies
Manifolds
Smooth manifolds
The medial axis and local feature size of a smooth manifold
The variation in normal vectors on smooth surfaces
Approximations of tangents by simplices

Restricted Delaunay Triangulations of Surface Samples
Restricted Voronoi diagrams and Delaunay triangulations
The Topological Ball Theorem
Distances and angles in ε-samples
Local properties of restricted Voronoi faces
Global properties of restricted Voronoi faces
The fidelity of the restricted Delaunay triangulation

Meshing Smooth Surfaces and Volumes
Delaunay surface meshing with a known local feature size
Topology-driven surface meshing
A practical surface meshing algorithm
Extensions: quality, smoothness, and polyhedral surfaces
Tetrahedral meshing of volumes bounded by smooth surfaces

Meshing Piecewise Smooth Complexes
Piecewise smooth complexes and their triangulations
An algorithm for meshing PSCs
The ball properties and the PSC Lemma
A proof of termination
Manifold patch triangulations and homeomorphism
Extensions: polygonal surfaces, quality, and tetrahedral

Bibliography

Index

Notes and Exercises appear at the end of each chapter.