Approximating Surfaces with Meshes
Ken Clarkson
March 10, 2005, 3:30PM, Wean 7220

Abstract:
How hard is it to approximate a smooth surface M with a piecewise-linear mesh? When M is the boundary of a convex body, remarkably tight bounds are known for the smallest Hausdorff distance possible when using a mesh with n simplices. In the case of more general surfaces, much less is understood. I'll show that the smallest distance, when M is a d-manifold, is O(S/n)^{2/d}, where S is the integral over M of the square root of the Gaussian curvature. (The constant factor here depends only on the dimension.) Also, under some reasonably general conditions on the surface and the mesh, this expression is also a lower bound, up to a constant factor. The upper bound construction distributes the vertices of the mesh in an "epsilon-net", in a metric based on directional curvature. The lower bound relates the volume of a simplex to its interpolation error.