Manifold reconstruction using tangential Delaunay complexes

Jean-Daniel Boissonnat (1) , Arijit Ghosh (2)

1 GEOMETRICA - Geometric computing
2 ACMU - Advanced Computing and Microelectronics Unit [Kolkata]

We give a provably correct algorithm to reconstruct a k-dimensional smooth manifold embedded in d-dimensional Euclidean space. The 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 and the technique of sliver removal by weighting the sample points. Differently from previous methods, we do not construct any subdivision of the d-dimensional ambient space. As a result, the running time of our al- gorithm 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.

Mots clés: Tangential Delaunay complex; weighted Delaunay triangulation; manifold reconstruc- tion; manifold learning; sampling conditions; sliver exudation

Domaines: Géométrie algorithmique [cs.CG]

Jean-Daniel Boissonnat, Arijit Ghosh. Manifold reconstruction using tangential Delaunay complexes. Discrete and Computational Geometry, 2014, 51 (1), pp.221-267. ⟨10.1007/s00454-013-9557-2⟩. ⟨hal-00932209⟩