Manifold Reconstruction using Tangential Delaunay Complexes

Jean-Daniel Boissonnat (Équipe Géométrica, Inria, Sophia-Antipolis)

We give a provably correct algorithm to reconstruct a k-dimensional manifold embedded in d-dimensional Euclidean space. Input to our algorithm is a point sample coming from an unknown manifold. Our approach is based on two main ideas : the notion of tangential Delaunay complex defined in [1, 2, 4], and the technique of sliver removal by weighting the sample points [3]. Differently from previous methods, we do not construct any subdivision of the embedding d-dimensional space. As a result, the running time of our algorithm depends only linearly on the extrinsic dimension d while it depends quadratically on the size of the input sample, and exponentially on the intrinsic dimension k. To the best of our knowledge, this is the first certified algorithm for manifold reconstruction whose complexity depends linearly on the ambient dimension. We also prove that for a dense enough sample the output of our algorithm is isotopic to the manifold and a close geometric approximation of the manifold.

This work was partially supported by the ANR project GAIA.


Joint work with Arijit Ghosh.

  1. J-D. Boissonnat and J. Flötotto. A coordinate system associated with points scattered on a surface. Journal of ACM, 36:161–174, 2004.
  2. J. Flötotto. A coordinate system associated to a point cloud issued from a manifold: definition, properties and applications. PhD thesis, Université of Nice Sophia-Antipolis, 2003.
  3. S-W Cheng, T. K. Dey, H. Edelsbrunner, M. A. Facello, and S-H Teng. Sliver exudation. Journal of ACM, 47:883–904, 2000.
  4. D. Freeman. Efficient simplicial reconstructions of manifolds from their samples. IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. 24, No. 10, 2002.
This document was translated from LATEX by HEVEA.