The authors introduce an algorithm that computes the cup product in the \(\mathbb{Z}_2\)-cohomology algebra of the boundary of a cubical complex associated to a 3D digital image. It can be effectively applied to any polyhedral complex embedded in \(\mathbb{R}^3\).
Let \((C_*(S), \partial)\) denote a chain complex of vector spaces over \(\mathbb{Z}_2\) where \(S=\{S_q\}\) consists of bases \(S_q\) of \(C_q(S)\). A chain contraction of \((C_*(S), \partial)\) to \((C_*(S'), \partial')\) is a tuple \((f,g,\phi, (S,\partial), (S',\partial'))\) consisting of chain maps \(f: C_*(S)\to C_*(S')\), \(g: C_*(S')\to C_*(S)\), and a chain homotopy \(\phi: C_*(S)\to C_*(S')\) such that \(fg=1_{C_*(S')}\) and \(\partial'\phi+\phi\partial= 1_{C_*(S)}+gf\). For any \(F\subseteq S\), an algebraic-topological model (AT-model) for \((C_*(S),\partial)\) is a chain contraction of the form \((f, g, \phi, (S,\partial), (F, 0_F))\) where \(0_F\) is the zero differential on \(C_*(F)\). The AT-model is denoted by \((f, g, \phi, (S,\partial), F)\). In this case, the map \(F_q\to H^q(S)\) given by \(\sigma\mapsto [\partial_{\sigma}f]\) extends to an isomorphism \(\partial_-: C_q(F)\approx H^q(S)\) by Proposition 2.5 (iii).
The authors consider regular cell complexes in the sense of W. S. Massey [A basic course in algebraic topology. New York etc.: Springer-Verlag (1991; Zbl 0725.55001)]. For a regular cell complex \(X=\{X_q\}\) and for an integer \(k\geq 0\), let \(X^{(k)}\) denote the \(k\)-skeleton. Let \(X\) and \(Y\) be regular cell complexes. A map \(f: X\to Y\) is cellular if \(f(X^{(k)})\subseteq Y^{(k)}\) for all \(k\). The geometric diagonal map \(\Delta_X^G: X\to X\times X\) is not cellular, but there exists a cellular map \(\Delta_X\) homotopic to \(\Delta_X^G\) by the cellular Approximation Theorem [A. Hatcher, Algebraic topology. Cambridge: Cambridge University Press (2002; Zbl 1044.55001), page 349].

{ Definition 3.1} Let \(X\) be a regular cell complex. A diagonal approximation on \(X\) is a cellular map \(\Delta_X: X\to X\times X\) with the following properties

●

i. \(\Delta_X\) is homotopic \(\Delta_X^G\).

●

ii. If \(\sigma\) is a cell of \(X\), then \(\Delta_X(\sigma)\subseteq \sigma\times \sigma\).

●

iii. \(\Delta_X\) extends to a chain map \(\Delta_X: C_*(X)\to C_*(X\times X)\approx C_*(X)\otimes C_*(X)\), called the coproduct induced by \(\Delta_X\).

Let \(X\) be a regular cell complex with a diagonal approximation \(\Delta_X: X\to X\times X\) and let \((f,g, \phi, (X,\partial), F)\) be an AT-model for \((C_*(X),\partial)\). Then \(C_*(F)\approx H_*(X)\approx H^*(X)\). Given classes \(\alpha\in H^p(X)\) and \(\alpha'\in H^q(X)\), there exist unique chains \(a=(\partial_-f)^{-1}(\alpha)\in C_p(F)\) and \(a'=(\partial_-f)^{-1}(\alpha')\in C_q(F)\) such that \(\alpha= [\partial_a f]\) and \(\alpha'= [\partial_{a'} f]\). The cup product of representative cocycles \(\partial_a f\) and \(\partial_{a'}f\) is the \((p+q)\)-cocycle defined on \(a''\in C_{p+q}(X)\) by \[ (\partial_a f\smile \partial_{a'} f)(a'')=m(\partial_a f \otimes \partial_{a'}f)\Delta_X(a''), \] where \(m\) is multiplication in \({\mathbb{Z}_2}\). The cup product of classes \(\alpha=[\partial_a f]\in H^p(X)\) and \(\alpha'=[\partial_{a'} f]\in H^q(X)\) is the class \[ \alpha \smile \alpha' = [\partial_a f \smile \partial_{a'}f]\in H^{p+q}(X). \] \((H^*(X),\smile)\) is an associative, graded commutative \(\mathbb{Z}_2\)-algebra. If \(X\) is a regular cell complex embedded in \(\mathbb{R}^3\), then \(H^p(X)=0\) for \(p>2\).
{Theorem 3.4} (Cohomology Structure Theorem) Let \(X\) be a regular cell complex embedded in \(\mathbb{R}^3\). Then \(H^*(X)\) is a direct sum of exterior algebras on \(1\)-dimensional generators.

If a regular cell complex \(X\) is constructed by attaching polytopes, then it is called a polyhedral complex. A 3D polyhedral complex is a polyhedral complex embedded in \(\mathbb{R}^3\). The main result of the paper gives an explicit formula for a diagonal approximation on each polygon in a 3D polyhedral complex \(X\):

{ Theorem 4.1} Let \(X\) be a 3D polyhedral complex. Arbitrarily number the vertices of \(X\) from \(1\) to \(n\) and represent a polygon \(p\) of \(X\) as an ordered \(k\)-tuple of vertices \(p=\langle i_1, \ldots, i_k\rangle\), where \(i_1= \min \{i_1, \ldots, i_k\}\), \(i_1\) is adjacent to \(i_k\), and \(i_j\) is adjacent to \(i_{j+1}\) for \(1<j<k\). There is a diagonal approximation on \(p\) given by \[ \begin{aligned} \widetilde{\Delta}_p(p) &= \langle i_1\rangle \otimes p + p\otimes \langle i_{m(k)}\rangle + \sum\limits_{j=2}^{m(k)-1} (u_2+ e_2 + \cdots + e_{j-1}+ \lambda_j e_j)\otimes e_j\\ &+ \sum\limits_{j=m(k)}^{k-1}[(1+\lambda_j) e_j+ e_{j+1}+ \cdots + e_{k-1}+ u_k]\otimes e_j, \end{aligned} \] where \(i_{m(k)}:= \max\{i_2, \ldots, i_k\}\), \(\lambda_j=0\) if and only if \(i_j<i_{j+1}\), \(\{u_j= \langle i_1, i_j\rangle\}_{2\leq j\leq k}\), and \(e_j= \langle i_j, i_{j+1} \rangle\) for all \({2\leq j\leq k-1}\).

A 3D digital image is a quadruple \(I= (\mathbb{Z}^3, 26, 6, B)\), where \(\mathbb{Z}^3\) is the underlying grid, the foreground \(B\) is a finite set of points in the grid, and the background is \(\mathbb{Z}^3\setminus B\). Here, it is fixed the binary 26-adjacency relation on \(B\) and 6-adjacency relation on \(\mathbb{Z}^3\setminus B\) defined as follows. Two points \((x,y,z)\) and \((x',y',z')\) of \(\mathbb{Z}^3\) are \(26\)-adjacent if \(1\leq (x-x')^2+(y-y')^2+(z-z')^2 \leq 3\). They are \(6\)-adjacent if \((x-x')^2+(y-y')^2+(z-z')^2 = 1\). The continuous analog \(CI\) of \(I\) is the set of unit cubes with faces parallel to the coordinate planes centered at the points of \(B\). These cubes are called the voxels of \(I\).
The cubical complex \(Q(I)\) associated to a 3D digital image \(I\) is the set of voxels of \(CI\) together with all of their faces (quadrangles, edges, and vertices). The subcomplex \(\partial Q(I)\) consists of all cells of \(Q(I)\) that are facets of exactly one cell of \(Q(I)\), and their faces.
Algorithm 5.2 presented in the paper gives a 3D polyhedral complex \(P(I)\) homeomorphic to \(\partial Q(I)\) whose maximal cells are polygons. This complex \(P(I)\) has fewer cells than \(\partial Q(I)\).
Using the formula given in Theorem 4.1, the authors give an algorithm for computing cup product in \(H^*(P(I))\) directly from the given combinatorics and analyze its computational complexity.