  In this paper, we study the shape reconstruction problem, when the shape we
wish to reconstruct is an orientable smooth d-dimensional submanifold of the
Euclidean space. Assuming we have as input a simplicial complex K that
approximates the submanifold (such as the Cech complex or the Rips complex), we
recast the problem of reconstucting the submanifold from K as a L1-norm
minimization problem in which the optimization variable is a d-chain of K.
Providing that K satisfies certain reasonable conditions, we prove that the
considered minimization problem has a unique solution which triangulates the
submanifold and coincides with the flat Delaunay complex introduced and studied
in a companion paper. Since the objective is a weighted L1-norm and the
contraints are linear, the triangulation process can thus be implemented by
linear programming.
