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 R^N. We will present a two-step approach in which the first step consists in building a rough approximation of the shape and the second step consists in extracting from this rough approximation a triangulation. Focusing on the first step, we shall explain how a rough approximation of the shape can be constructed under the form of a simplicial complex whose vertices are the data points. We shall review conditions under which this rough approximation is guaranteed to be homotopy-equivalent to the shape. We will then turn our attention to the second step. Assuming we have as input a simplicial complex that provides a homotopy-equivalent approximation of a manifold, we will reformulate the problem of searching for a triangulation as a convex minimization problem, whose objective function is a weighted l1-norm. In particular, we use a well-known trick in combinatorics which consists in enlarging the search space, replacing the set of triangulations contained in the input simplicial complex by a vector space formed by the d-chains of that simplicial complex. We show that, under appropriate conditions, the solution of our minimization problem is indeed a triangulation of the manifold and that this triangulation coincides with the tangential Delaunay complex, whose definition we shall recall.

This is a joint work with André Lieutier.