410 Pages 173 B/W Illustrations
    by Chapman & Hall

    Written by authors at the forefront of modern algorithms research, Delaunay Mesh Generation demonstrates the power and versatility of Delaunay meshers in tackling complex geometric domains ranging from polyhedra with internal boundaries to piecewise smooth surfaces. Covering both volume and surface meshes, the authors fully explain how and why these meshing algorithms work.

    The book is one of the first to integrate a vast amount of cutting-edge material on Delaunay triangulations. It begins with introducing the problem of mesh generation and describing algorithms for constructing Delaunay triangulations. The authors then present algorithms for generating high-quality meshes in polygonal and polyhedral domains. They also illustrate how to use restricted Delaunay triangulations to extend the algorithms to surfaces with ridges and patches and volumes with smooth surfaces.

    For researchers and graduate students, the book offers a rigorous theoretical analysis of mesh generation methods. It provides the necessary mathematical foundations and core theoretical results upon which researchers can build even better algorithms in the future.

    For engineers, the book shows how the algorithms work well in practice. It explains how to effectively implement them in the design and programming of mesh generation software.

    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 Rd
    The Delaunay triangulation in Rd
    The optimality of the Delaunay triangulation in Rd
    Bistellar flips and the flip algorithm
    Three-dimensional constrained Delaunay triangulations

    Algorithms for Constructing Delaunay Triangulations in R3
    A dictionary data structure for tetrahedralizations
    Delaunay vertex insertion in R3
    Biased randomized insertion orders
    Optimal point location by a conflict graph in R3
    Point location by walking
    The gift-wrapping algorithm in R3
    Inserting a vertex into a CDT in R3
    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
    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



    Notes and Exercises appear at the end of each chapter.


    Siu-Wing Cheng is a professor in the Department of Computer Science and Engineering at the Hong Kong University of Science and Technology. Professor Cheng is an advisory committee member of the International Symposium on Algorithms and Computation and a board member of the Asian Association for Algorithms and Computation. His research interests include computational geometry, mesh generation, manifold reconstruction, and algorithms. He earned a Ph.D. in computer science from the University of Minnesota, Twin Cities.

    Tamal K. Dey is a professor of computer science at Ohio State University, where he leads the Jyamiti group, which develops software such as the well-known Cocone software for surface reconstruction and DelPSC software for mesh generation. He previously held faculty positions at Indiana University-Purdue University and IIT Kharagpur and research positions at the University of Illinois and Max-Planck Institute. His research interests include computational geometry and topology and their applications in graphics and geometric modeling. He earned a Ph.D. from Purdue University.

    Jonathan Shewchuk is a professor in the Department of Electrical Engineering and Computer Sciences at the University of California, Berkeley. He is best known for his Triangle software for high-quality triangular mesh generation, which won the 2003 James Hardy Wilkinson Prize in Numerical Software, and his paper "Introduction to the Conjugate Gradient Method without the Agonizing Pain." He received his Ph.D. in computer science from Carnegie Mellon University.