Jonathan Richard Shewchuk
University of California Berkeley
Homepage
Talk title
Better Sampling Bounds for Restricted Delaunay Triangulations, with Applications to Surface Meshing
Abstract
The restricted Delaunay triangulation (RDT) is a well-established way of generating good-quality triangulations on curved surfaces. Researchers have developed a theory of surface sampling to determine how we should sample points on a surface to guarantee that an RDT is a topologically correct and geometrically accurate approximation of the surface, equipping geometers to rigorously prove the correctness of algorithms for surface reconstruction and surface mesh generation. It is well known that if the point set is a sufficiently dense sample of a smooth surface, then the union of the restricted Delaunay triangles is homeomorphic to the surface. I show that an epsilon-sample with epsilon < 0.3245 suffices. This is a significant improvement on the previous best bound, showing that RDTs are useful, not merely theoretical. I also review how RDTs are used to generate guaranteed-quality meshes of smooth surfaces.
Biography
Jonathan Shewchuk is a Professor in the Department of Electrical Engineering and Computer Sciences at UC Berkeley. He is best known for his software Triangle for high-quality triangular mesh generation, which won the 2003 James Hardy Wilkinson Prize in Numerical Software, and his "Introduction to the Conjugate Gradient Method Without the Agonizing Pain." His book "Delaunay Mesh Generation," written jointly with Siu-Wing Cheng and Tamal Dey, is available from CRC Press.