J.-D. Boissonnat, L. J. Guibas, and S. Y. Oudot. Manifold Reconstruction in Arbitrary Dimensions using Witness Complexes. Proc. 23rd ACM Sympos. on Comput. Geom., pages 194-203, 2007. Full version in Discrete and Computational Geometry, 42(1):37-70, 2009 (pdf).

Abstract:

It is a well-established fact that the witness complex is closely related to the restricted Delaunay triangulation in low dimensions. Specifically, it has been proved that the witness complex coincides with the restricted Delaunay triangulation on curves, and is still a subset of it on surfaces, under mild sampling assumptions. Unfortunately, these results do not extend to higher-dimensional manifolds, even under stronger sampling conditions. In this paper, we show how the sets of witnesses and landmarks can be enriched, so that the nice relations that exist between both complexes still hold on higher-dimensional manifolds. We also use our structural results to devise an algorithm that reconstructs manifolds of any arbitrary dimension or co-dimension at different scales. The algorithm combines a farthest-point refinement scheme with a vertex pumping strategy. It is very simple conceptually, and it does not require the input point sample $W$ to be sparse. Its time complexity is bounded by $c(d) |W|^2$, where $c(d)$ is a constant depending solely on the dimension $d$ of the ambient space.

Bibtex: 

@inproceedings{bgo-mraduwc-07
, author =      {J.-D. Boissonnat and L. J. Guibas and S. Y. Oudot}
, title =       {Manifold Reconstruction in Arbitrary Dimensions using Witness Complexes}
, booktitle =   {Proc. 23rd ACM Sympos. on Comput. Geom.}
, year =        {2007}
}