J.-D. Boissonnat, S. Y. Oudot. Provably Good Sampling and Meshing of Surfaces. Graphical Models, volume 67, issue 5, pages 405-451, September 2005.

Abstract:

The notion of r-sample, introduced by Amenta and Bern, has proven to be a key concept in the theory of sampled surfaces. Of particular interest is the fact that, if E is an r-sample of a C^2-continuous surface S for a sufficiently small r, then the Delaunay triangulation of E restricted to S is a good approximation of S, both in a topological and in a geometric sense. Hence, if one can construct an r-sample, one also gets a good approximation of the surface. Moreover, correct reconstruction is ensured by various algorithms.
In this paper, we introduce the notion of loose r-sample. We show that the set of loose r-samples contains and is asymptotically identical to the set of r-samples. The main advantage of loose r-samples over r-samples is that they are easier to check and to construct. We also present a simple algorithm that constructs provably good surface samples and meshes. Given a C^2-continuous surface S without boundary, the algorithm generates a sparse r-sample E and at the same time a triangulated surface Dels(E). The triangulated surface has the same topological type as S, is close to S for the Hausdorff distance, and can provide good approximations of normals, areas and curvatures. A notable feature of the algorithm is that the surface needs only to be known through an oracle that, given a line segment, detects whether the segment intersects the surface and, in the affirmative, returns the intersection points. This makes the algorithm useful in a wide variety of contexts and for a large class of surfaces.

Bibtex: 

@article{bo-pgsms-05,
 author = {J.-D. Boissonnat and S. Y. Oudot},
 title = {Provably good sampling and meshing of surfaces},
 journal = {Graphical Models},
 volume = {67},
 number = {5},
 month = {September},
 year = {2005}
 }