Efficient Construction of 2-Chains with a Prescribed Boundary

Let $Omega$ be a bounded domain of ${mathbb R}^3$ whose closure $overline{Omega}$ is polyhedral, and let ${mathcal{T}}$ be a triangulation of $overline{Omega}$. We devise a fast algorithm for the computation of homological Seifert surfaces of any 1-boundary of ${mathcal{T}}$, namely, 2-chains of ${mathcal{T}}$ whose boundary is $gamma$. Assuming that the boundary of $Omega$ is sufficiently regular, we provide an explicit formula for a homological Seifert surface of any 1-boundary $gamma$ of ${mathcal{T}}$. It is based on the existence of special spanning trees of the complete dual graph and on the computation of certain linking numbers associated with those spanning trees. If the triangulation ${mathcal{T}}$ is fine, the explicit formula is too expensive to be used directly. To overcome this difficulty, we adopt an easy and very fast elimination procedure, which sometimes fails. In such a case a new unknown can be computed using the explicit formula and the elimination algorithm restarts. The numerical experiments we performed illustrate the efficiency of the resulting algorithm even when the homology of $Omega$ is not trivial and the triangulation ${mathcal{T}}$ of $overline{Omega}$ consists of millions of tetrahedra.