Delaunay Triangulation of Manifolds

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 for a perturbed point set provided the transition functions are bi-lipschitz with a constant close to 1, and the original 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 output complex is also a delaunay triangulation of its vertices with respect to this piecewise-flat metric.