×

Uh-oh, it looks like your Internet Explorer is out of date.

For a better shopping experience, please upgrade now.

Delaunay Mesh Generation / Edition 1
     

Delaunay Mesh Generation / Edition 1

by Siu-Wing Cheng, Tamal K. Dey, Jonathan Shewchuk
 

ISBN-10: 1584887303

ISBN-13: 9781584887300

Pub. Date: 12/14/2012

Publisher: Taylor & Francis

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

Overview

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.

Product Details

ISBN-13:
9781584887300
Publisher:
Taylor & Francis
Publication date:
12/14/2012
Series:
Chapman & Hall/CRC Computer and Information Science Series
Pages:
410
Product dimensions:
7.10(w) x 10.00(h) x 1.10(d)

Table of Contents

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 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
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.

Customer Reviews

Average Review:

Post to your social network

     

Most Helpful Customer Reviews

See all customer reviews