Algorithms Seminar 2003

The notion of $\varepsilon$-sample, as 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 $\varepsilon$-sample of a smooth surface $S$ for a sufficiently small $\varepsilon$, then the Delaunay triangulation of $E$ restricted to $S$, $\dels(E)$, is a good approximation of $S$, both in a topological and in a geometric sense. Hence, if one can construct an $\varepsilon$-sample, one also gets a good approximation of the surface. Moreover, correct reconstruction is ensured by various algorithms.

In this talk, we introduce the notion of $\varepsilon$-fine sample. We show that the set of $\varepsilon$-fine samples contains and is asymptotically identical to the set of $\varepsilon$-samples. The main advantage of $\varepsilon$-fine samples over $\varepsilon$-samples is that they are easier to check and to construct. Our construction algorithm is a variant of Chew's surface meshing algorithm. Given a smooth closed surface $S$, the algorithm generates a sparse $\varepsilon$-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 remarkable 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 an intersection point and the distance to the skeleton at that point. This makes the algorithm useful in a wide variety of contexts and for a large class of surfaces.

joint work with Steve Oudot