Manifold reconstruction from point samples

We present an algorithm to "reconstruct" a smooth k-dimensional manifold M embedded in an Euclidean space ℝd from a "sufficiently dense" point sample from the manifold. The algorithm outputs a simplicial manifold that is homeomorphic and geometrically close to M. The running time is O(n log n) where n is the number of points in the sample (the multiplicative constant depends exponentially on the dimension though).