Manifold reconstruction based on Coxeter triangulations of the ambient Euclidean space

par Siargey Kachanovich (Inria Sophia Antipolis)

jeudi 14 juin 2018, 10:30 → 11:30 Europe/Paris

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.