Lexicographic optimal chains and manifold triangulations
David Cohen‐Steiner, André Lieutier, Julien Vuillamy · HAL (Le Centre pour la Communication Scientifique Directe) · 2019
Given a simplicial complex $K$, we consider the problem of finding a simplicial $d$-chain minimal in a given homology class.This is sometimes referred to as the {\em Optimal Homologous Chain Problem} (OHCP). We consider here simplicial chains with coefficients in $\mathbb{Z}/2 \mathbb{Z}$ and the particular situation where, given a total order on $d$-simplices $\sigma_1< \ldots <\sigma_n$, the weight of simplex $i$ is $2^i$. In this case,the comparison of chains is a lexicographic ordering. Similarly, we consider the problem of {\em finding a minimal chain for a prescribed boundary}. We show that, for both problems, the same matrix reduction algorithm used for the computation of homological persistence diagrams, applied to the filtration induced by the order on $p$-simplices, allows a $O(n^3)$ worst case time complexity algorithm.Second,we consider OHCP in the particular case where $K$ is a $(d+1)$-pseudo-manifold, for example when it triangulates a $(d+1)$-sphere. In this case, there is a $O(n \log n)$ algorithm which can be seen, by duality, as a {\em lexicographic minimum cut} in the dual graph of $K$. Third, we introduce a total order on $n$-simplices for which, when the points lie in the $n$-Euclidean space, the support of the lexicographic-minimal chain with the convex hull boundary as boundary constraint is precisely the $n$-dimensional Delaunay triangulation, or in a more general setting, the regular triangulation of a set of weighted points. Fourth, we apply the lexicographic min-cut on the dual graph of the $3$-dimensional Delaunay complex of a points cloud in $\mathbb{R}^3$. This gives in practice an efficient algorithm providing minimal solutions that, while inheriting the optimality for $2$-dimensional Delaunay triangulations, reveals to create pertinent and convincing meshes for surface reconstruction, in particular in the case of noisy point clouds with non uniform densities and outliers, such as those produced by physical captures or Structure From Motion algorithms. Last, it is known that a \v{C}ech complex with the right parameter over a point cloud sampling a compact connected $C^2$ manifold embedded in Euclidean space, if the sampling density is high enough with respect to the manifold reach, captures the homotopy type of the manifold and in particular its fundamental class.In the particular case of $2$-manifolds, we show that, under good sampling conditions, the lexicographic minimal chain representative of the image of the fundamental class in the \v{C}ech complex provides a triangulation of the manifold.