Browse Books

Reviewer: Minette Carl

At the outset, one must understand that the author is a world-renowned expert in computational geometry and topology, who is best known in academia for the creation of alpha-shapes, which have many applications in computer graphics and computer-aided design (CAD) and computer-aided manufacturing (CAM) systems. In addition, he has made other significant contributions in three-dimensional (3D) modeling. Therefore, it is no surprise that this text is a wonderful introduction for applying these mathematical disciplines to mesh generation. The current monograph addresses the needs of students at the graduate or advanced undergraduate level. It is well written, includes thoughtful exercises, demonstrates the concepts with appropriate figures, and simplifies for the reader mathematical material that could otherwise be overwhelming. Mesh generation is an essential component of many fields including finite element methods. These applications require the partitioning of a geometric model (planar or curved domains) into a finite number of elements adjacent to one another. Structured meshes are composed of a regular grid topology. Unstructured meshes can have a variable number of elements meeting at any given point. Delaunay triangulations typically provide unstructured meshes. The author presents simplicial complexes (not based on simplicial sets from homotopy theory) as a tool for representing surfaces and solids. Such complexes are topological-space constructed by connecting points, line segments, and triangles (and their multidimensional versions) in a simple manner. The book comprises seven chapters and provides a wonderful tutorial for anyone interested in meshes, whether from the fields of CAD/CAM, finite elements, or computer graphics. Chapter 1 studies Voronoi diagrams and Delaunay triangulations from both a theoretical and a practical view. Triangular meshes with Delaunay refinements are presented in chapter 2. Analysis is provided for geometric results and corresponding lower/upper bounds. The discussion on combinatorial topology (chapter 3) introduces simplicial complexes and general topological spaces. Since subdivisions of the complexes are constructed, Euler characteristic properties are calculated and applied to the notion of shelling. The next three chapters deal with 3D modeling. The goal of chapter 4 is to approximate a 3D shape with a triangulated surface with fewer triangles than are provided by standard methods. The algorithm presented is greedy in nature and contracts edges until the number of remaining triangles is within a user-defined tolerance level (and error measure, when possible). This requires the application of combinatorial topological concepts to the surface. Delaunay tetrahedrization (chapter 5) extends the two-dimensional triangulation process to three dimensions. Without much effort, this can be extended to higher dimensions, although the focus of this chapter is three dimensions with tetrahedron elements. Here too, a randomized algorithm constructs a Delaunay tetrahedrization by adding one point at a time. Likewise, chapter 6 extends meshes to three dimensions using tetrahedron elements. A "particularly annoying" type of tetrahedron is discussed with ways to remove it from Delaunay meshes. Twenty-three "open" problems are collected in chapter 7. It is interesting to note that two of them (union of disks and intersection of disks) have actually been solved, but the author includes them anyway because the presentation of the problem differs significantly from the approach of the eventual solution. The other 21 problems are meant to stimulate the reader to think about the unknown, and are related to the information expressed in earlier chapters. The problems are perhaps a small subset of "known" unknown problems, but were selected from the literature based on simplicity to describe and relate to the material studied. Mesh generation requires a combination of approaches from different fields (mathematics, computer science, and engineering) to solve its problems. This book develops combined methods from these disciplines in a clear and methodical manner. The book provides straightforward tutorials on fundamental concepts, which then build up to proposed solutions and algorithms. The text makes for interesting reading for students and professionals alike, and elucidates an area that could otherwise be daunting to some. Online Computing Reviews Service