Lexicographic optimal chains and manifold triangulations
This talk will consist in three parts. In the first part we will describe algorithms for the computation of lexicographic minimal chains in an abstract setting. 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 $\Z/2 \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 {\em 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 $d$-simplices, allows a $\BigO(n^3)$ worst case time complexity algorithm.
In the particular case where $K$ is a $(d+1)$-pseudo-manifold,there is a $\BigO(n \log n)$ algorithm which can be seen, by duality, as a {\em lexicographic minimum cut} in the dual graph of $K$.
The second part will show how a carefully chosen total order on simplices allows to retrieve regular triangulations in euclidean spaces, as well as the triangulation of positive reach $2$-manifolds as the support of lexicographic minimal chains.
We see that each part is motivated by the other.
In a last part we will consider two open questions suggested by the preceding results.
Results from a joined work with David Cohen-Steiner and Julien Vuillamy.
Thanks for ongoing works and discussions with:
Dominique Attali, Jean-Daniel Boissonnat, Mathijs Wintraecken