  We present an algorithm for producing Delaunay triangulations of manifolds.
The algorithm can accommodate abstract manifolds that are not presented as
submanifolds of Euclidean space. Given a set of sample points and an atlas on a
compact manifold, a manifold Delaunay complex is produced provided the
transition functions are bi-Lipschitz with a constant close to 1, and the
sample points meet a local density requirement; no smoothness assumptions are
required. If the transition functions are smooth, the output is a triangulation
of the manifold.
  The output complex is naturally endowed with a piecewise flat metric which,
when the original manifold is Riemannian, is a close approximation of the
original Riemannian metric. In this case the ouput complex is also a Delaunay
triangulation of its vertices with respect to this piecewise flat metric.
