In many practical situations, the shape of interest is only known through a finite set of data points. Given as input those data points, it is then natural to try to construct a triangulation of the shape, that is, a set of simplices whose union is homeomorphic to the shape. This problem has given rise to many research works in the computational geometry community, motivated by applications to 3D model reconstruction and manifold learning.
In this talk, we focus on one particular instance of the shape reconstruction problem, in which the shape we wish to reconstruct is an orientable smooth $d$-manifold embedded in $\mathbb{R}^N$. We reformulate the problem of searching for a triangulation as a convex minimization problem, whose objective function is a weighted $\ell_1$-norm. I will then present the result in [1] which says that, under appropriate conditions, the solution of our minimization problem is indeed a triangulation of the manifold and that this triangulation coincides with a variant of the tangential Delaunay complex.
This is joint work with André Lieutier.
[1] Dominique Attali and André Lieutier. Delaunay-like triangulation of smooth orientable sub-manifolds by least $\ell_1$-norm minimization. In 38th International Symposium on Computational Geometry (SoCG'22), Berlin, Germany, June 7-10, 2022. [download].