Browse Books

Reviewer: Joseph J. ORourke

This is a worthy successor to Edelsbrunner's 2001 book [1], published in the same "Cambridge Monographs" series, tracking that book in digestible length, mathematical rigor, clarity, and focus on Voronoi diagrams and Delaunay triangulations. Although the title is accurate, 20 percent of the book is on curve reconstruction, while the remaining 80 percent addresses the more challenging surface reconstruction. All major results described were obtained within the last decade, many in collaboration with the author of this book. The goal is reconstruction of a curve Γ or surface Σ from a discrete set of unorganized sample points P , as might be obtained from a laser scanner, for example. Throughout, results are based on η-samples: those whose density guarantees that every sample point x has a another sample point p "nearby," in that | x - p | is no more than η times the distance of x from the medial axis of Γ or Σ. The reason the Delaunay triangulation Del P plays a role for a curve Γ is that all "correct edges" (those we want to reconstruct) are in Del P . This leads to the crust algorithm, later improved to the nearest neighbor (NN) crust algorithm, which guarantees correct reconstruction of Γ for η < 1/3 by using both Del P and NN. The reason the Voronoi diagram Vor P plays a central role for a surface Σ is that the Voronoi cell containing a sample point p is long and thin, with the direction of elongation approximating (for dense samples) the surface normal direction n p at p . Indeed, it is a remarkable result that for η < 0.18, the dual subset of Del P of the cells of Vor P that intersect Σ is homeomorphic (deformable) to Σ. Unfortunately, Σ is the unknown, and so this does not immediately yield an algorithm. However, the approximate normal n p can be used to define a "cocone," which spreads out rays rougly perpendicular to n p (within ± 22.5°), capturing the triangles of Del P closest to Σ. Carefully extracting a manifold from these triangles ultimately leads to one of the major achievements of this field (and the core of this book): the cocone algorithm, which guarantees reconstruction of Σ?point-wise, normal-wise, homeomorphic, and isotopic?for η < 0.05. Note the progressively smaller η values as problem difficulty increases. The second half of the book extends this surface reconstruction algorithm to handle the practical situations that arise from real data: undersampling, surfaces with boundary, noisy samples, hole-filling (watertight reconstructions), and smoothing via moving least squares (MLS) surfaces. One MLS theorem requires η < 0.004, reflecting the intricacy of the proof. A final chapter presents the novel wrap algorithm of Edelsbrunner, which reconstructs by peeling away simplices of Del P based on the Morse flow complex. The book is based on a computer science graduate course and demands graduate-level sophistication, especially in mathematics. Many wonderful Computational Geometry Algorithms Library (CGAL) computed figures are used to illustrate the performance of the algorithms on real data sets. Online Computing Reviews Service