Building Triangulations Using epsilon-nets

This work addresses the problem of approximating a manifold by a simplicial mesh, and the related problem of building triangulations for the purpose of piecewise-linear approximation of functions. It has long been understood that the vertices of such meshes or triangulations should be "well-distributed," or satisfy certain "sampling conditions." This work clarifies and extends some algorithms for finding such well-distributed vertices, by showing that they can be regarded as finding epsilon-nets or Delone sets in appropriate metric spaces. In some cases where such Delone properties were already understood, such as for meshes to approximate smooth manifolds that bound convex bodies, the upper and lower bound results are extended to more general manifolds; in particular, under some natural conditions, the minimum Hausdorff distance for a mesh with n simplices to a d-manifold M is Theta((int_M sqrt {|kappa(x)|}/n)^{2/d}) as n-->infinity, where kappa(x) is the Gaussian curvature at point x in M. We also relate these constructions to Dudley's approximation scheme for convex bodies, which can be interpreted as involving an epsilon-net in a metric space whose distance function depends on surface normals.