This chapter gives an introduction to the computational geometry of surfaces. The main motivation is to provide effective algorithms to construct PL approximations of surfaces. Instead of surveying the many approaches that have been proposed in the literature, we focus on provably correct methods and, among them, on methods based on a fundamental data structure that has been extensively studied in computational geometry, the Voronoi diagram of a finite set of points. Given n points (also called sites) of R~d, the associated Voronoi diagram subdivides R~d into regions, each region consisting of the points of R~d that are closer to one of the sites. In a first part (sections 13.2-13.3), we introduce Voronoi diagrams and their dual Delau-nay triangulations. We establish a connexion between Voronoi diagrams and polytopes that allows to derive tight combinatorial bounds and efficient algorithms to construct Voronoi diagrams. This first part is a (very brief) introduction to computational geometry. The interested reader will find more material in the textbooks devoted to the subject. In a second part (sections 13.4-13.5), we show how Voronoi diagrams and Delaunay triangulations can be used to sample and approximate a surface. The main tool is the concept of Delaunay triangulation restricted to a surface. Under some sample condition, we will show that the restricted Delaunay triangulation of a surface S is a good approximation of S, both in a topological and a geometric sense. We will present and analyze an algorithm to compute such an approximation, and present some results.
展开▼
