Séminaire Calcul Formel

Manifold reconstruction based on Coxeter triangulations of the ambient Euclidean space

by Siargey Kachanovich (Inria Sophia Antipolis)

Salle XR203 (Bâtiment XLIM)

Salle XR203

Bâtiment XLIM

We present an experimental algorithm for manifold reconstruction, which takes as input a point cloud sampled from a manifold with positive reach and outputs a simplicial complex which is homotopy equivalent to the manifold. The time complexity and the space complexity are polynomial in ambient dimension and depend on the intrinsic dimension $k$ of the manifold as $O(2^k)$, which improves the $O(2^{k^2})$ time and space complexities of tangential complex. The algorithm is based on Coxeter triangulations, space-filling triangulations generated by a single simplex via consecutive flips. We have seen in experiments that a series of collapses can be applied to the output of the first algorithm to find a triangulation of the manifold.