# Lexicographic optimal chains and manifold triangulations

Date: Tuesday, February 11, 2020 14:00 - 15:00
Speaker: André Lieutier (Dassault Systemes)
Location: Mondi Seminar Room 2, Central Building
Series: Mathematics and CS Seminar
Host: Herbert Edelsbrunner

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