Cups products in Z2-cohomology of 3D polyhedral complexes

arXiv:1207.2346v3 [cs.CV] 9 Jul 2013 CUPS PRODUCTS IN Z2-COHOMOLOGY OF 3D POYHEDRAL COMPLEXES ROCIO GONZALEZ-DIAZ, JAVIER LAMAR, AND RONALD UMBLE Abstract. Let I= (Z3,26,6, B) be a 3D digital image, let Q(I) be the associated cubical complex and let ∂Q(I) be the subcomplex of Q(I) whose maximal cells are the quadrangles of Q(I) shared by a voxel of Bin the foreground – the object under study – and by a voxel of Z3rBin the background – the ambient space. We show how to simplify the combinatorial structure of ∂Q(I) and obtain a 3D polyhedral complex P(I) homeomorphic to ∂Q(I) but with fewer cells. We introduce an algorithm that computes cup products on H∗(P(I); Z2) directly from the combinatorics. The computational method introduced here can be effectively applied to any polyhedral complex embedded in R3. 1. Introduction This paper completes the work proposed in our prequel-abstract [9] by providing additional insights, examples, proofs and a corrected version of formula (2) in Theorem 4.1. Unless explicitly indicated otherwise, all modules in the discussion that follows are assumed to have Z2coefficients. Roughly speaking, a regular cell complex is a collection of q-dimensional cells glued together in such a way that non-empty intersections of cells is a cell [13, page 348]. A regular cell complex is a polyhedral complex if its q-cells are q-polytopes [20, pages 24–25]. In particular, a cubical complex is a polyhedral complex whose q-cells are q-cubes. In this paper we are especially interested in 3D polyhedral complexes, which are polyhedral complexes embedded in R3. The cellular chain complex of a regular cell complex Xis the chain complex (C∗(X), ∂), where C∗(X) is the graded Z2-vector space generated by the cells of Xand ∂is the cellular boundary; the cellular cochain complex (C∗(X), δ) is its linear dual. The cellular cohomology H∗(X) is the quotient Ker δ/ Im δ, whose coset representatives are cocycles supported on the connected components, noncontractible loops, and surfaces bounding the cavities of X. Moreover, H∗(X) is a graded commutative algebra whose cup product encodes certain relationships among the generators and enhances our ability to distinguish between objects. For example, H∗(S1∨S1∨S2) and H∗(S1×S1) are isomorphic as vector spaces but not as algebras since cup products of 1-dimensional classes vanish in H∗(S1∨S1∨S2) but not in H∗(S1×S1). Indeed, S1∨S1∨S2and S1×S1are not homeomorphic and have quite different topological properties. Date: July 9, 2013. Key words and phrases. Cohomology, cup product, diagonal approximation, digital image, polyhedral complex, polygon. This research was funded in part by the Spanish Ministry of Economy and Competitiveness under project MTM2012-32706 and a Millersville University faculty research grant. 1 2 ROCIO GONZALEZ-DIAZ, JAVIER LAMAR, AND RONALD UMBLE In this paper, we introduce new formulas for computing cup products directly from the combinatorics of a 3D polyhedral complex. When Xis a regular cell complex homeomorphic to but with fewer cells than the boundary surface of a 3D digital image, our formulas improve computational efficiency in certain problems related to 3D image processing. To date, the cup product has seen limited application in 3D image processing. In [10, 11], R. Gonzalez-Diaz and P. Real used their 14-adjacency algorithm and the standard formulation in [27] to compute cup products on the simplicial complex associated with a given 3D digital image. At about the same time, T. Kaczynski, M. Mischaikow and M. Mrozek [15] showed how to compute the homology of a 3D digital image directly from the voxels thought of as a cubical complex. Their algorithm, which applies techniques from linear algebra, demonstrates that the homology of a cubical complex is actually computable. R. Gonzalez-Diaz, Jimenez and B. Medrano [8] introduced a method for computing cup products directly from a cubical complex associated with a given 3D digital image (no additional subdivisions are necessary). More recently, motivated by problems in high-dimensional data analysis, T. Kaczynski and M. Mrozek [17] gave an algorithm for computing the cohomology algebra of a cubical complex of arbitrary dimension; they are currently in the process of implementing their algorithm. In the context of persistent cohomology, A. Yarmola [34] discussed the computation of cup products in the cohomology of a finite simplicial complex over a field. For a geometrical interpretation of cohomology in the context of digital images, we refer the reader to [7]. The cup product arises naturally from a diagonal approximation on a regular cell complex X, which is a map ∆ : X→X×Xthat preserves cellular structure and is homotopic to the geometric diagonal map ∆G(σ) = σ×σ. In [22], D. Kravatz constructed a diagonal approximation on a general polygon and used it to compute cup products on the cohomology of closed compact orientable surfaces thought of as identification spaces of 2n-gons. Unfortunately Kravatz’s diagonal depends upon a particular indexing of the vertices and cannot be applied in more general settings. Consequently, we introduce a generalization of Kravatz’s diagonal, which is independent of indexing (Theroem 4.1). A problem that frequently arises in 3D image processing is to encode the boundary surface of a 3D digital image as a set of voxels. The most popular approach to this problem uses a triangulation. While triangles are combinatorially simple, and visualization of triangulated surfaces is supported by existing software, the number of triangles required is often large and the computational analysis is correspondingly slow. It is desirable, therefore, to consider approximations with simpler combinatorics that can be analyzed more efficiently. Indeed, given any covering of a 2-dimensional surface with polygons, we show how to iteratively merge adjacent polygons and reduce the number of polygons in the covering. Having done so, we apply our generalized diagonal approximation to compute cup products directly from the combinatorics. Although our strategy for merging adjacent cells is not new (see [2, 3, 6, 16], for example), the notion that cup products can be computed using a diagonal approximation that varies from cell-to-cell is novel indeed. For testing purposes, a Matlab implementation of our method is posted at the URL below1. 1http://grupo.us.es/cimagroup/imagesequence2cupproduct.zip CUPS PRODUCTS IN Z2-COHOMOLOGY OF 3D POYHEDRAL COMPLEXES 3 More precisely, let Z3denote the set of positive integer lattice points in R3and consider a 3D digital image I= (Z3,26,6, B), where B⊂Z3is the foreground, Bc=Z3rBis the background, 26 is the adjacency relation for the foreground and 6 for the background (see [21]). Represent Ias the set of unit cubes (voxels) centered at the points of Btogether with all of their faces, and let Q(I) be the associated cubical complex. Let ∂Q(I) be the subcomplex of Q(I) whose maximal cells are the quadrangles of Q(I) shared by a voxel of Band a voxel of Z3rB. We show how to merge adjacent quadrangles into a polygonal face to produce a polyhedral complex homeomorphic to ∂Q(I) with fewer cells. Our procedure differs from existing simplification procedures whose approximating complexes either fail to be cell complexes (see [15], for example), are simpler triangulations of given triangulations, or are simplifications of triangulated manifolds. A complete list of surface simplifications appear in [14]. The paper is organized as follows: Section 2 reviews some standard definitions from algebraic topology. Section 3 reviews the notions of diagonal approximation and cup product, defines the diagonal approximation induced from a given diagonal approximation via a chain contraction, and derives some of its important properties. Our main result, which appears in Section 4 as Theorem 4.1, gives an explicit formula for a diagonal approximation on each polygon in a 3D polyhedral complex X. Since H3(X)≡0, the cup product defined in terms of our combinatorial diagonal is sufficient for computing the cohomology algebra H∗(X). In Section 5 we introduce our reduction algorithm, which reduces a cubical Q(I) to a homeomorphic polyhedral complex P(I) with fewer cells. Using the explicit formula given in Theorem 4.1, we give an algorithm for computing cup products on H∗(P(I)) directly from the given combinatorics and analyze its computational complexity. Conclusions and some ideas for future work are presented in Section 6. 2. Standard Definitions from Algebraic Topology Unless explicitly indicated otherwise, all modules in the discussion that follows are assumed to have Z2coefficients. Let S={Sq}be a graded set. A q-chain is a finite formal sum of elements of Sq(mod 2 addition). The q-chains together with the operation of vector addition form the vector space Cq(S) of q-chains of S. The chains of Sis the graded vector space C∗(S) = {Cq(S)}, and a chain complex of Sis a pair (C∗(S), ∂), where ∂={∂q:Cq(S)→Cq−1(S)}is a square zero linear map called the boundary operator. Aq-chain a∈Cq(S) is a q-cycle if ∂q(a) = 0; it is a q-boundary if there is a (q+1)- chain a′′ such that ∂q+1(a′′) = a. Two q-cycles aand a′are homologous if a+a′is aq-boundary. Let Zq(S) and Bq(S) denote the q-cycles and q-boundaries of S, respectively. Then Bq(S)⊆Zq(S) since ∂∂ = 0. The quotient Hq(S) = Zq(S)/Bq(S) is the qth homology of Sand the graded vector space H∗(S) = {Hq(S)}is the homology of S. An element of Hq(S) is a class [a] := a+Bq(S); the cycle ais a representative cycle of the class [a]. The dimension of Hq(S) is called the qth Betti number and is denoted by bq. Let (C∗(S), ∂) and (C∗(S′), ∂′) be chain complexes. A linear map of graded vector spaces f={fq:Cq(S)→Cq(S′)}(also denoted by f:C∗(S)→C∗(S)) is a chain map if fq−1∂q=∂′ qfqfor all q. Let f, g :C∗(S)→C∗(S′) be chain maps. A chain homotopy from fto gis a linear map of graded vector spaces 4 ROCIO GONZALEZ-DIAZ, JAVIER LAMAR, AND RONALD UMBLE φ={φq:Cq(S)→Cq+1(S′)}(also denoted by φ:C∗(S)→C∗+1(S)) such that ∂′ q+1φq+φq−1∂q=fq+gqfor all q, or simply ∂′φ+φ∂ =f+g. Achain contraction of (C∗(S), ∂)to (C∗(S′), ∂′) is a tuple (f, g, φ, (S, ∂),(S′, ∂′)) consisting of chain maps f:C∗(S)→C∗(S′), g:C∗(S′)→C∗(S), and a chain homotopy φ:C∗(S)→C∗+1(S) such that fg =1C∗(S′)and ∂′φ+φ∂ =1C∗(S)+ gf. Note that fand gare chain homotopy equivalences by definition. The idea of a chain contraction is due to H. Cartan [4], whose “little constructions” are contractions of the bar construction onto a tensor product of exterior algebras, polynomial algebras, and truncated polynomial algebras. Remark 2.1.If (f, g, φ, (S, ∂),(S′, ∂′)) is a chain contraction, the chain homotopy equivalence ginduces and isomorphism H∗(S′)≈H∗(S). Let nbe a positive integer. A topological space Xis an n-dimensional regular cell complex if Xcan be constructed inductively in the following way (see [26, Page 243]): •Choose a finite discrete set X(0), called the 0-skeleton of X; the elements of X(0) are called 0-cells of X. •If the (q−1)-skeleton X(q−1) has already been constructed, construct the q-skeleton X(q)by attaching finitely many closed q-disks {σq i}to X(q−1) via homeomorphisms {fi:∂σq i→Eq−1 i}, where E(q−1) iis a subcomplex of X(q−1) homeomorphic to the (q−1)-dimensional sphere. Once attached, σq iis called a q-cell of X. •The induction terminates at the nth stage with X=X(n). Aq-cell σ′of Xis a facet of a (q+ 1)-cell σof Xif σ′⊂σ. A maximal cell of Xis not a facet of any cell of X. Regular cell complexes have particularly nice properties, for example, their homology is effectively computable [26, Page 243]. When a regular cell complex Xis constructed by attaching polytopes, we refer to Xas a polyhedral complex. In particular, a 3D polyhedral complex is a polyhedral complex embedded in R3. Let Xand Ybe regular cell complexes. A continuous map f:X→Yof regular cell complexes is cellular if f(X(q))⊆Y(q)for each q. Thus if σis a q-cell of X, then f(σ) is a union of cells {eqi} ⊂ Ywith qi≤qfor all i. A cellular map f:X→Y induces a map f:C∗(X)→C∗(Y) in the obvious way. Let X={Xq}denote the graded set of cells of a regular cell complex X. The cellular chains of X, denoted by C∗(X), is the graded vector space generated by the elements of X. The cellular chain complex of Xis the chain complex (C∗(X), ∂), where ∂is the linear extension of the cellular boundary. The cellular homology of X, denoted by H∗(X), is the homology of the graded set X. Definition 2.2. Let Xbe a regular cell complex and let γbe an r-cell of X contained in the boundary of exactly two (r+ 1)-cells µand µ′of X. Let X′be the cell complex obtained from Xby replacing µand µ′with the single cell µ′′ =µ∪µ′ so that X′= (Xr{γ, µ, µ′})∪ {µ′′}and ∂′ q:Cq(X′)→Cq−1(X′) is the linear extension of the map defined on generators σ∈ X′by ∂′ q(σ) =    ∂r+1 (µ+µ′), q =r+ 1 and σ=µ′′, ∂r+2(σ) + µ+µ′+µ′′, q =r+ 2 and µor µ′lies in ∂r+2(σ), ∂q(σ),otherwise. Then µand µ′have merged into µ′′ along γ. CUPS PRODUCTS IN Z2-COHOMOLOGY OF 3D POYHEDRAL COMPLEXES 5 0−cochain c0Ac0={v1} 1−cochain c1Ac1={e1, e4} 1−coboundary δ(c0)Aδ(c0)={e3, e4} 1−cocycle x1Ax1={e1, e2} 1−cocycle y1Ay1={e1, e2, e3, e4} Cohomologous cocycles x1and y1; since y1+x1=δ(c0) Figure 1. A cubical complex with 9 vertices, 12 edges and 3 squares (in gray). Proposition 2.3. If regular cell complexes Xand X′are related as in Definition 2.2, then H∗(X)≈H∗(X′). Proof. Consider a pair of cellular maps f:X→X′and g:X′→Xwith the properties •f(γ) = f(µ) = ∂µ rint(γ), f(µ′) = µ′′, and f(σ) = σ, if σ∈Xand σ6=γ, µ, µ′; •g(µ′′) = µ∪µ′and g(σ) = σ, if σ∈X′and σ6=µ′′. Then fand ginduce chain maps f:C∗(X)→C∗(X′) and g:C∗(X′)→C∗(X) such that •f(γ) = γ+∂(µ), f(µ) = 0, f(µ′) = µ′′, and f(σ) = σ, if σ∈ X and σ6=γ, µ, µ′; •g(µ′′) = µ+µ′and g(σ) = σ, if σ∈ X ′and σ6=µ′′. There is a chain contraction (f, g, φ, (X, ∂),(X′, ∂′)), with φ:C∗(X)→C∗+1(X) given by φ(γ) = µand zero otherwise, which is, in fact, a reduction of chain complexes in the sense of [16]. The conclusion follows by Remark 2.1.  The dual space of Cq(S) is denoted by Cq(S) and its elements are called qcochains. Thus a q-cochain cassigns a scalar value to each generator in Sq= {σ1,...,σnq}. Let A={σ∈Sq|c(σ) = 1}; then cis the characteristic function IA:Sq→Z2. Let a∈Cq(S) be a q-chain. Then a=σi1+···+σirfor some indices 1≤i1<··· < ir≤nq. The cochain dual to ais the linear map a∗:Cq(S)→Z2 such that a∗(σi) = 1 if and only if i∈ {i1,...,ir}. The vector space of cochains of Sis the graded vector space C∗(S) = {Cq(S)}. The coboundary operator is the linear map δ={δq:Cq(S)→Cq+1(S)}defined on a q-cochain cby δq(c) = c∂q+1; then δδ = 0 and the pair (C∗(S), δ) is the cochain complex dual to (C∗(S), ∂). A q-cochain cis a q-cocycle if δq(c) = 0. A q-cochain bis a q-coboundary if there exists a (q−1)-cochain csuch that b=δq−1(c). Two q-cocycles cand c′are cohomologous if c+c′is a q-coboundary. The q-cocycles Zq(S) and q-coboundaries Bq(S) satisfy 6 ROCIO GONZALEZ-DIAZ, JAVIER LAMAR, AND RONALD UMBLE Bq(S)⊆Zq(S) since δδ = 0 (for concrete examples of cocyles and coboundaries, see the table in Figure 1). The quotient Hq(S) = Zq(S)/Bq(S) is the qth cohomology of Sand the graded vector space H∗(S) = {Hq(S)}is the cohomology of S. An element of Hq(S) is a class [c] := c+Bq(S). Remark 2.4.Since the ground ring Z2is a field, the homology and cohomology of a finite graded set Sare isomorphic and torsion free (see [27, pages 325, 332– 333]). Furthermore, given a chain contraction (f, g, φ, (S, ∂),(S′, ∂′)), there is a map ∂−f:C∗(S′)→C∗(S) that sends an element σ∈S′to the cochain ∂σf defined by ∂σf(µ) = 1,if σis a non-zero summand of f(µ) ; 0,otherwise; The cochain ∂σfis supported on the subspace generated by all µ∈Ssuch that σ is a summand of f(µ). Let Sbe a graded set, let F⊆S, and let 0Fdenote the zero differential on C∗(F). An Algebraic-Topological model (AT-model) for (C∗(S), ∂) is a chain contraction of the form (f, g, φ, (S, ∂),(F, 0F)); since 0F≡0, we often drop the symbol 0Fand write (f, g, φ, (S, ∂), F). An AT-model for (C∗(S), ∂) always exists with computational complexity no worse than O(m3), where m= #S(see [10, 11] for details). We note that the algorithm presented in [16] for computing homology by reduction of chain complexes is a precursor of the AT-model. Proposition 2.5. Let (f, g, φ, (S, ∂), F)be an AT-model for (C∗(S), ∂). i. If σ∈Fq,then g(σ)represents a class in Hq(S). ii. The map Fq→Hq(S)given by σ7→ [g(σ)] extends to an isomorphism Cq(F)≈Hq(S). iii. The map Fq→Hq(S)given by σ7→ [∂σf]extends to an isomorphism ∂−f:Cq(F)≈Hq(S). Proof. In view of Remark 2.4, the proof is immediate.  Proposition 2.6. Let (f, g, φ, (S, ∂),(S′, ∂′)) be a chain contraction. i. If (f′, g′, φ′,(S, ∂), F)is an AT-model for (C∗(S), ∂), then (f′g, fg′, fφ′g, (S′, ∂′), F)is an AT-model for (C∗(S′), ∂′). ii. If (f′′, g′′, φ′′,(S′, ∂′), F′)is an AT-model for (C∗(S′), ∂′), then (f′′f, gg′′, φ+gφ′′f, (S, ∂), F′)is an AT-model for (C∗(S), ∂). Proof. Observe that f′∂≡0, ∂g′≡0, f′′∂′≡0 and ∂′g′′ ≡0. Hence i. f′gfg′=f′(∂φ +φ∂ +1C∗(S))g′=f′g′=1C∗(F)and ∂fφ′g+fφ′g∂ =f(∂φ′+φ′∂)g=f(1C∗(S)+g′f′)g=1C∗(S′)+fg′f′g. ii. f′′fgg′′ =f′′ 1C∗(S′)g′′ =f′′g′′ =1C∗(F′)and ∂(φ+gφ′′f) + (φ+gφ′′f)∂=∂φ +φ∂ +g(∂φ′′ +φ′′∂)f =∂φ +φ∂ +g(1C∗(S′)+g′′f′′)f =1C∗(S)+gg′′f′′f.  CUPS PRODUCTS IN Z2-COHOMOLOGY OF 3D POYHEDRAL COMPLEXES 7 3. Cup Products and Diagonal Approximations In this section we review the definitions and related notions we need to compute the cup product on the cellular cohomology H∗(X) of a 3D polyhedral complex X. Agraded algebra is a vector space Aequipped with an associative multiplication m:A⊗A→Aof degree zero and a unit. The cellular cohomology H∗(X) of a regular cell complex Xis a graded commutative algebra with respect to the cup product defined below in this section. A differential graded algebra (DGA) is a chain complex (A, d) in which Ais a graded algebra and da derivation of the product, i.e., dm =m(d⊗1+1⊗d) (see [25, page 190]). Let d⊗denote the linear extension of dto the n-fold tensor product. A homotopy associative algebra is identical to a DGA to every respect except that the multiplication m on Ais homotopy associative, i.e., there is a chain homotopy m3:A⊗3→Asuch that m(m⊗1) + m(1⊗m) = dm3+m3d⊗. Let τ:A⊗A→A⊗Adenote the twisting isomorphism given by τ(a⊗a′) = a′⊗a. The multiplication mis homotopy commutative if there is a chain homotopy h:A⊗A→Asuch that m+mτ =dh +hd⊗. Over a field, and Z2in particular, a graded coalgebra C is the linear dual of a graded algebra, and comes equipped with a coassociative coproduct ∆ : C→C⊗Cof degree zero and a counit. A differential graded coalgebra (DGC) is the linear dual of a DGA. Thus a DGC is a chain complex (C, d) in which Cis a graded coalgebra and dis a coderivation of the coproduct, i.e., ∆d= (d⊗1+1⊗d)∆. A homotopy coassociative (cocommutative) coproduct is the linear dual of a homotopy associative (commutative) product. The geometric diagonal on a topological space Xis the map ∆G X:X→X×X defined by ∆G X(σ) = σ×σ. If Xis a regular cell complex, ∆G Xis typically not a cellular map, but nevertheless, the Cellular Approximation Theorem [13, page 349]) guarantees the existence of a cellular map ∆Xhomotopic to ∆G X. Roughly speaking, such maps are “diagonal approximations”, the precise definition of which now follows (for a categorical treatment see [31, page 250]). Definition 3.1. Let Xbe a regular cell complex. A diagonal approximation on Xis a cellular map ∆X:X→X×Xwith the following properties: i. ∆Xis homotopic to ∆G X. ii. If σis a cell of X, then ∆X(σ)⊆σ×σ. iii. ∆Xextends to a chain map ∆X:C∗(X)→C∗(X×X)≈C∗(X)⊗C∗(X), called the coproduct induced by ∆X. Item (iii) in Definition 3.1 implies that the cellular boundary map ∂extends to a coderivation of ∆X. Thus (C∗(X), ∂, ∆X) is a DGC whenever ∆Xis coassociative. Various examples of diagonal approximations appear in [29]. Example 3.2. Let sn=h0,1,...,nidenote the n-simplex. The Alexander- Whitney (A-W) diagonal approximation on snextends to a chain map ∆s:C∗(sn)→ C∗(sn)⊗C∗(sn) defined on the top-dimensional generator by ∆s(sn) = n X i=0 h0,...,ii ⊗ hi, . . . , ni (see [31, page 250]). The chain map ∆sis a strictly coassociative, homotopy cocommutative coproduct on C∗(sn). Thus (C∗(sn), ∂, ∆s) is a DGC for each n. 8 ROCIO GONZALEZ-DIAZ, JAVIER LAMAR, AND RONALD UMBLE The 0-cube I0is the single point 0, the 1-cube I1is the unit interval I = [0,1], and the n-cube Inis the n-fold Cartesian product I × · · · × I with n≥1 factors. A cell of Inis an n-fold Cartesian product u1× · · · × un∈ {0,1,I}×n. Example 3.3. The Serre diagonal approximation on Inextends to a chain map ∆I:C∗(In)→C∗(In)⊗C∗(In) defined on the top-dimensional generator by ∆I(0) = 0 ⊗0 and ∆I(In) = (0 ⊗I + I ⊗1)⊗n (see [30, page 441]). Let ac ⊗bd denote (a⊗b)⊗(c⊗d); then for example, ∆II2= (0 ⊗I + I ⊗1) ⊗(0 ⊗I + I ⊗1) = 0 0 ⊗I I + 0 I ⊗I 1 + I 0 ⊗1 I + I I ⊗1 1. Let 0′= I and I′= 1; then for n≥1 we obtain ∆I(In) = X u1···un∈{0,I}⊗n u1···un⊗u′ 1···u′ n. Again, ∆Iextends to a strictly coassociative, homotopy cocommutative coproduct ∆I:C∗(In)→C∗(In)⊗C∗(In) and (C∗(In), ∂, ∆I) is a DGC for each n. Let Xbe a regular cell complex, let ∆X:X→X×Xbe a diagonal approximation, and let (f, g, φ, (X, ∂), F) be an AT-model for (C∗(X), ∂). Then C∗(F)≈H∗(X)≈H∗(X) by Remark 2.4 and Proposition 2.5. Given classes α∈Hp(X) and α′∈Hq(X),there exist unique chains a= (∂−f)−1(α)∈Cp(F) and a′= (∂−f)−1(α′)∈Cq(F) such that α= [∂af] and α′= [∂a′f].The cup product of representative cocycles ∂afand ∂a′fis the (p+q)-cocycle defined on a′′ ∈Cp+q(X) by (∂af ⌣ ∂a′f) (a′′) = m(∂af⊗∂a′f)∆X(a′′), where mdenotes multiplication in Z2. The cup product of classes α= [∂af]∈ Hp(X) and α′= [∂a′f]∈Hq(X) is the class α ⌣ α′= [∂af ⌣ ∂a′f]∈Hp+q(X) (see [31, page 251]). In practice, we compute α ⌣ α′in the following way: {g(σ) : σ∈Fp+q}is a complete set of representative (p+q)-cycles. For each σ∈Fp+q, let λσ= (∂af ⌣ ∂a′f)g(σ) and let σ∗denote the cochain dual to g(σ). Then (1) α ⌣ α′=X σ∈Fp+q λσ[σ∗]. The cup product on H∗(X) is a bilinear operation with unit. If ∆Xis homotopy coassociative, (H∗(X), ⌣) is a graded algebra; if ∆Xis also homotopy cocommutative, the algebra (H∗(X), ⌣) is graded commutative. In particular, if Xis a simplicial (cubical) complex, the A-W diagonal ∆s(Serre diagonal ∆I) induces an associative, graded commutative cup product on H∗(X). In particular, if Xis a regular cell complex embedded in R3then Hn(X) = 0 for all n > 2 (see [1, chapter 10]). Thus if x, y ∈H∗(X) are homogeneous elements of positive degree and x ⌣ y 6= 0, then x, y ∈H1(X). Furthermore, since the squaring map H1(X)→H2(X) coincides with the Bockstein, a non-zero squaring map implies that Z2is a direct summand of both H1(X;Z) and H2(X;Z), which is impossible since H2(X;Z) = H0(S3rX, Z) by Alexander duality and H0(S3rX, Z) is torsion free. Therefore all cup-squares vanish in H2(X), and we have proved: CUPS PRODUCTS IN Z2-COHOMOLOGY OF 3D POYHEDRAL COMPLEXES 9 Theorem 3.4 (Cohomology Structure Theorem).Let Xbe a regular cell complex embedded in R3. Then H∗(X)is a direct sum of exterior algebras on 1-dimensional generators. Remark 3.5.The argument that cup-squares vanish in H2(X) given above for regular cell complexes Xembedded in R3, is due to E. Wofsey [33]. Let Xand X′be regular cell complexes, let (f, g, φ, (X, ∂),(X′, ∂′)) be a chain contraction, and let (f′, g′, φ′,(X′, ∂′), F′) be an AT-model for C∗(X′). Given σ′∈ F′ pand µ′∈F′ q, consider α′= [∂σ′f′] and β′= [∂µ′f′] in H∗(X′),and recall that (f′f, gg′, φ+gφ′f, (X, ∂), F′) is an AT-model for C∗(X) (Proposition 2.6, part (ii)). Let α= [∂σ′f′f] and β= [∂µf′f] in H∗(X). Since f:C∗(X)→C∗(X′) is a chain homotopy equivalence, the map f∗:H∗(X′)→H∗(X) given by f∗[u] = [u◦f] is an algebra isomorphism. Thus f∗(α′) = f∗[∂σ′f′] = [∂σ′f′f] = α, f∗(β′) = β, and α ⌣ β =f∗(α′)⌣ f∗(β′) = f∗(α′⌣ β′). In summary we have proved: Proposition 3.6. If Xand X′are regular cell complexes, and (f, g, φ, (X, ∂),(X′, ∂′)) is a chain contraction, then for α′, β′∈H∗(X′)and α=f∗(α′), β =f∗(β′)we have f∗(α′⌣ β′) = α ⌣ β. Definition 3.7.Let Xand X′be regular cell complexes, let ∆X:C∗(X)→ C∗(X)⊗C∗(X) be the coproduct induced by a diagonal approximation, let (f, g, φ, (X, ∂),(X′, ∂′)) be a chain contraction, and let (f′, g′, φ′,(X′, ∂′), F′) be an AT- model for C∗(X′). The induced coproduct on C∗(X′) is the chain map e ∆X′:= (f⊗f)◦∆X◦g:C∗(X′)→C∗(X′)⊗C∗(X′). Proposition 3.8. Let (f, g, φ, (X, ∂),(X′, ∂′)) be the explicit chain contraction in the proof of Proposition 2.3. Then the induced coproduct e ∆X′defined in Definition 3.7 restricts to a diagonal approximation. Proof. We first check that e ∆X′(µ′′)⊆µ′′ ×µ′′. Identify the generators σ∈ X and σ′∈ X′with the corresponding cells σ∈Xand σ′∈X′, and identify (f⊗f) (σ⊗σ) with (f×f) (σ×σ). Then e ∆X′(µ′′) = [(f×f)◦∆X◦g] (µ′′) = (f×f) [∆X(µ+µ′)] = (f×f)(∆X(µ) + ∆X(µ′)). By assumption, ∆X(σ)⊆σ×σfor each cell σ⊆X; since fvanishes on µwe have (f×f)(∆X(µ) + ∆X(µ′)) = (f×f)∆X(µ′)⊆µ′′ ×µ′′. Next we show that e ∆X′is homotopic to the geometric diagonal map ∆G X′. Choose a homotopy h:X×I→X×Xfrom ∆G Xto ∆X; then at each σ∈Xwe have h(σ, 0) = ∆G X(σ) and h(σ, 1) = ∆X(σ).Consider the composition h′= (f×f)◦h◦(g×1) : X′×I→X′×X′. Then at each σ′∈X′we have h′(σ′,0) = [(f×f)◦h◦(g×1)] (σ′,0) = (f×f) [h(g(σ′),0)] = (f×f) ∆G X(g(σ′)) = (f×f) (g(σ′)×g(σ′)) =fg(σ′)×fg(σ′) = σ′×σ′= ∆G X′(σ′) 16 ROCIO GONZALEZ-DIAZ, JAVIER LAMAR, AND RONALD UMBLE 0 10 20 30 40 50 60 70 80 90 0 10 20 30 40 50 60 70 80 90 0 2 4 6 8 10 12 14 Figure 6. The cubical complex ∂Q(microCT ). In their split-and-merge procedure, F. Schmitt and X. Chen [32] use their “merging stage” procedure to join adjacent “nearly coplanar”regions. In [24], J. Lee shows how to simplify a triangular mesh by deleting vertices – the result is a new triangular mesh. In [18], A. Kalvin, et al., show how to reduce the complexity of a polygonal mesh by merging adjacent coplanar rectangles. In [12], A. Gourdon shows how to simplify a polyhedron by sequentially removing edges while preserving the Euler characteristic. And in [19], R. Klein, et al., give a procedure for iteratively removing vertices from a triangulated manifold, to produce a triangulated polyhedron (all vertices in a manifold are non-critical). Example 5.4.Figure 5 displays a sequence of 14 2D digital images of size 85 ×85 produced by a micro-CT of a trabecular bone. Superposition produces a cubical complex we denote by Q(microCT ) with 85 ×85 ×14 cubes. Its boundary ∂Q(microCT ) pictured in Figure 6 consists of 24582 quadrangles. An application of Algorithm 5.2 to ∂Q(microCT ) using Terminating Condition 1 produces a polyhedral complex with 2158 polygons (see Figure 7.a). On the other hand, if we apply Algorithm 5.2 using Terminating Condition 2, we obtain a polyhedral complex with 12802 polygons (see Figure 7.b). Now, consider the output P(I) of Algorithm 5.2. The chain complex (C∗(P(I)), ∂) can be described as follows: •The vector space Cq(P(I)) is generated by the q-cells of P(I). •The value of ∂q:Cq(P(I)) →Cq−1(P(I)) on a q-cell is the sum of its facets. •The boundary of a sum of q-cells is the sum of their boundaries. Example 5.5.Consider the 3D polyhedral complex P(microCT ) (Figure 7.b) produced by an application of Algorithm 5.2 to ∂Q(microCT ) (Figure 6). The Betti numbers of P(microCT ) obtained by computing an AT-model for P(microCT ) are b0= 8, b1= 9 and b2= 17. These results count the number of connected components, holes and cavities. Representative 1-cycles are pictured in Figure 8. CUPS PRODUCTS IN Z2-COHOMOLOGY OF 3D POYHEDRAL COMPLEXES 17 (a) (b) 0 10 20 30 40 50 60 70 80 90 0 10 20 30 40 50 60 70 80 90 0 5 10 15 0 10 20 30 40 50 60 70 80 90 0 10 20 30 40 50 60 70 80 90 0 5 10 15 Figure 7. (a) The 3D polyhedral complex P(microCT ) for 10 edges as lower bound on p∈P(microCT ). (b) The 3D polyhedral complex P(microCT ) preserving geometry. 5.2. Computing the Cohomology Algebra H∗(P(I)).Given a 3D digital image I, consider a 3D polyhedral complex P(I) homeomorphic to ∂Q(I). All nontrivial cup products in H∗(P(I)) are products of distinct 1-cocycles by Theorem 3.4. To compute cup products in H∗(P(I)), we first compute an AT-model 18 ROCIO GONZALEZ-DIAZ, JAVIER LAMAR, AND RONALD UMBLE 20 30 40 50 60 70 80 90 10 20 30 40 50 60 70 80 90 0 2 4 6 8 10 12 14 1 α 2 α 3 α 4 α 5 α 6 α 7 α 8 α 9 α Figure 8. Representative 1-cycles on the 3D polyhedral complex P(microCT ) displayed in Figure 7.b. (f, g, φ, (P(I), ∂), F) for (C∗(P(I)), ∂) using Algorithm 2 given in [11]. If F1= {µ0,...,µb1−1}and F2={γ0,...,γb2−1}, the cup products can be stored in a b1(b1−1)/2×b2matrix A. The entry A(i+j, k), 0 ≤i < j ≤b1−1, 0 ≤k≤b2−1, is: A(i+j, k) = m(∂µif⊗∂µjf)(e ∆P)g(γk), where e ∆Pis the induced diagonal approximation given by Theorem 4.1 Thus by Equation 1 we have [∂µif]⌣[∂µif] = b2−1 X k=0 (A(i+j, k)) ·[γ∗ k] where γ∗ kis the cochain dual to g(γk). The matrix Ais symmetric since the cup product is graded commutative (e ∆Pis homotopy cocommutative by Proposition 3.9). Let mbe the number of voxels of I, let nbe the number of cells of P(I), and let kbe the maximum number of vertices in a polygon of P(I). To determine the computational complexity of the computation of the cohomology algebra H∗(P(I)), note that: •Computing the number of critical vertices of ∂Q(I) is O(m) since the number of cells of Q(I) is at most 27 ·m. •The computational complexity of Algorithm 5.2, which produces the 3D polyhedral complex P(I), is O(m) since, in the worst case, the number of edges in P(I) incident to a non-critical vertex v∈P(I) is 6 and the number of 2-cells of Nvis 12. CUPS PRODUCTS IN Z2-COHOMOLOGY OF 3D POYHEDRAL COMPLEXES 19 Figure 9. Left: 3D polyhedral complex T. Right: 3D polyhedral complex T′. •The computational complexity of the algorithm given in [11] to obtain an AT-model (f, g, φ, (P(I), ∂), F ) for (C∗(P(I)), ∂) is O(n3). •The complexity to compute a row of Ais at most O(n·k2·b2 1), since for a fixed γ∈F2,g(γ) has at most nsummands, e ∆phas ksummands, and for a 1-cell σ∈P(I), f(σ) has at most b1summands. Thus the overall computational complexity for computing the cohomology algebra H∗(P(I)) is O(m+n3+b2·n·k·b2 1), where biis the ith Betti number. Furthermore, since k << n << m and bℓ<< n << m,ℓ= 1,2, overall complexity in most cases is O(n3) and at worst is O(m3) when no simplification of ∂Q(I) is given. Example 5.6.Starting from the results obtained in Example 5.5, we applied the formula given in Theorem 4.1 to representative 1-cocycles on the 3D polyhedral complex P(microCT ) (Figure 7.b) and displayed their (non-trivial) cup products in the following table (αiαjdenotes αi⌣ αj): α2α4α2α5α2α9α3α8α4α5 β16 11111 The table below illustrates the dramatic improvement in computational efficiency realized if cup products are computed on the 3D polyhedral complex T′obtained by removing faces and non-critical vertices of the 3D polyhedral complex Tof a (hollow) double torus (see Figure 9). 3D Polyhedral Number of Time (in seconds) complex 2-cells to compute the cup product T1638 28.00 sec. T′46 1.04 sec. The following table displays the cup products on the polyhedral complex T′(see Figure 9. Right). α1α2α1α3α1α4α2α3α2α4α3α4 β0 1 1 0 1 0 20 ROCIO GONZALEZ-DIAZ, JAVIER LAMAR, AND RONALD UMBLE 0 10 20 30 40 50 60 70 10 20 30 40 50 60 70 1 2 3 4 5 0 10 20 30 40 50 60 70 10 20 30 40 50 60 70 0 2 4 6 001 005004 003 002 (a) (b) Figure 10. a) 3D polyhedral complex P(DBrain); b) Representative 1-cycles. Example 5.7.We obtained the 3D digital image DBrain in Figure 10.a by binarizing and resizing the first five frames in J. Mathers DICOM Example Files containing MR images of the brain2. The boundary of DBrain contains 7084 quadrangles. Algorithm 5.2 with Terminating Condition 2 produces a 3D polyhedral complex P(DBrain) with 2433 polygons (see Figure 10.a). The betti numbers b0= 2, b1= 19 and b2= 2 are determined by computing an AT-model (f, g, φ, (P(DBrain), ∂), F) for (C∗(P(DBrain)), ∂). Denote by {α1,...,α19}and {β1, β2}, the respective bases for H1(DBrain) and H2(DBrain); dual representative 1-cycles are pictured in Figure 10.b. The non-trivial cup products displayed in the table below indicate the high level of topological complexity in the polyhedral 2http://www.mathworks.com/matlabcentral/fileexchange/2762-dicom-example-files/ CUPS PRODUCTS IN Z2-COHOMOLOGY OF 3D POYHEDRAL COMPLEXES 21 complex P(DBrain). α1α8α2α3α2α5α2α17 α3α5α3α6α3α7α3α9α3α13 β21 1 1 1 1 1 1 1 1 α5α6α5α7α5α9α5α13 α6α12 α6α13 α6α16 α8α19 β21 1 1 1 1 1 1 1 α9α17 α11α12 α12α19 α13α15 α14α18 α16α19 α18α19 β21111111 6. Conclusions and Plans for Future Work Given a 3D digital image I, we have formulated the cup product on the cohomology of the 3D polyhedral complex P(I) obtained by simplifying the cubical complex ∂Q(I). The algorithm presented here can be applied to any 3D polyhedral complex. The ultimate goal of this work is to compute cup products on the cohomology of any regular n-dimensional cell complex over a general ring directly from its combinatorial structure (without subdivisions). Our strategy will be to apply some standard topological constructions such as forming quotients, taking Cartesian products, and merging cells. Acknowledgments. We wish to thank Jim Stasheff and the anonymous referees for their helpful suggestions, which significantly improved the exposition, and Manuel Eugenio Herrera Lara–Universidad Complutense de Madrid for providing the 14 micro-CT images in Figure 5. References [1] Alexandroff P., Hopf H.: Topologie I. Springer, 1935 [2] Argawal P.K., Suri S.: Surface Approximation and Geometric Partitions. SIAM Journal on Computing 27 (4), pages 1016–1035 (1998) [3] Bronnimann H., Goodrich M.T.: Almost Optimal Set Covers in Finite VC-dimension. Discrete and Computational Geometry 14, pages 263–279 (1995) [4] Cartan H.: D´etermination des alg`ebres H∗(π, n;Z2et H∗(π, n;Z2) groupes stables modulo p. S´eminaire Henri Cartan, tome 7, no. 1, exp. no. 10, pages 1–8 (1954-1955) [5] Cohen, M. M.: A Course in Simple-homotopy Theory, Berlin, New York: Springer-Verlag, 1973 [6] Das G., Goodrich M.T.: On the Complexity of Optimization Problem for 3D Convex Polyhedra and Decision Trees. Computational Geometry, Theory and Applications 8, pages 123–137 (1997) [7] Gonzalez-Diaz, R., Ion A., Iglesias-Ham M., Kropatsch W.: Invariant Representative Cocycles of Cohomology Generators using Irregular Graph Pyramids. Computer Vision and Image Understanding 115 (7), pages 1011–1022 (2011) [8] Gonzalez-Diaz R., Jimenez M.J., Medrano B.: Cohomology Ring of 3D Photographs. Int. Journal of of Imaging Systems and Technology 21, pages 76–85 (2011) [9] Gonzalez-Diaz R., Lamar J., Umble R.: Cup Products on Polyhedral Approximations of 3D Digital Images. Proc. of the 14th Int. Conf. on Combinatorial Image Analysis (IWCIA 2011), LNCS 6636, pages 107–119 (2011) [10] Gonzalez-Diaz R., Real P.: Towards Digital Cohomology. Proc. of the 11th Int. Conf. on Discrete Geometry for Computer Imagery, (DGCI 2003). LNCS 2886, pages 92–101 (2003) [11] Gonzalez-Diaz R., Real P.: On the Cohomology of 3DDigital Images. Discrete Applied Math. 147, pages 245–263 (1997) [12] Gourdon A.: Simplification of Irregular Surface Meshes in 3D Medical Images. Computer Vision, Virtual Reality, and Robotics in Medicine (CVRMed 95), pages 413419 (1995) [13] Hatcher A.: Algebraic Topology. Cambridge University Press, 2002 22 ROCIO GONZALEZ-DIAZ, JAVIER LAMAR, AND RONALD UMBLE [14] Heckbert P., Garland M.: Survey of Polygonal Surface Simplification Algorithms. Multiresolution surface modeling (SIGGRAPH ’97 Course notes 25), 1997. ftp.cs.cmu.edu/afs/cs/project/anim/ph/paper/multi97/release/heckbert/simp.pdf [15] Kaczynski T., Mischaikow K., Mrozek M.: Computational Homology. Applied Mathematical Sciences 157, Springer-Verlag, 2004 [16] Kaczynski T., Mrozek M., ´ Slusarek M.: Homology Computation by Reduction of Chain Complexes. Computers & Mathematics with Applications 35 (4), pages 59–70 (1998) [17] Kaczynski T., Mrozek M.: The Cubical Cohomology Ring: An Algorithmic Approach Foundations of Computational Mathematics (published online: 26 October 2012), pages 1-30 (2012) [18] Kalvin A.D., Cutting C.B., Haddad B., Noz M.E.: Constructing Topologically Connected Surfaces for the Comprehensive Analysis of 3D Medical Structures. Medical Imaging V: Image Processing (SPIE) 1445, pages 247-258 (1991) [19] Klein R., Liebich G., Strasser W.: Mesh Reduction with Error Control. Seventh IEEE Visualization Conference (VIS ’96), IEEE, pages 311–318 (1996) [20] Kozlov D.N.: Combinatorial Algebraic Topology. Algorithms and Computation in Mathematics 21, Springer, 2008 [21] Kong T.Y., Roscoe A.W., Rosenfeld A.: Concepts of Digital Topology. Topology and its Applications 46 (3), pages 219–262 (1992) [22] Kravatz, D.: Diagonal Approximations on an n-gon and the Cohomology Ring of Closed Compact Orientable Surfaces. Senior Thesis. Millersville University Department of Mathematics, 2008. http://www.millersville.edu/~rumble/StudentProjects/Kravatz/finaldraft.pdf [23] Latecki L.J.: 3D Well-Composed Pictures. Graphical Models and Image Processing 59 (3), pages 164–172 (1997) [24] Lee J.: A Drop Heuristic Conversion Method for Extracting Irregular Network for Digital Elevation Models. Proc. of American Congress on Surveying and Mapping (GIS/LIS 89) 1, pages 30-39 (1989) [25] Mac Lane S.: Homology. Springer-Verlag, New York, 1967. [26] Massey W.S.: A Basic course in Algebraic Topology. Graduate Texts in Mathematics. Springer-Verlag, 1991. [27] Munkres J.R.: Elements of Algebraic Topology. Addison-Wesley Co., 1984. [28] Peltier S., Ion A., Kropatsch W.G., Damiand G., Haxhimusa Y.: Directly Computing the Generators of Image Homology Using Graph Pyramids. Image and Vision Computing 27 (7), pages 846–853 (2009) [29] Saneblidze S., Umble R. Diagonals on the Permutahedra, Multiplihedra and Associahedra. J. Homology, Homotopy and Appl. 6 (1), pages 363–411 (2004) [30] Serre J.P.: Homologie Singuli`ere des Espaces Fibr`es, applications. Ann. Math. 54, pages 429–501 (1951) [31] Spanier E.H.: Algebraic Topology. McGraw-Hill, 1966. [32] Schmitt F., Chen X.: Fast Segmentation of Range Images into Planar Regions. Proc. of Conf. on Computer Vision and Pattern Recognition (CVPR 91), IEEE Comput. Soc. Press, pages 710–711 (1991) [33] Wofsey, E.: mathoverflow posting, April 3, 2013. http://mathoverflow.net/questions/126310/ [34] Yarmola A.: Persistence and Computation of the Cup Product. Senior Honor Thesis. Department of Mathematics, Stanford University, 2010. http://math.stanford.edu/theses/Yarmola%20Honors%20Thesis.pdf [35] Zomorodian A.: The Tidy Set: a Minimal Simplicial Set for Computing Homology of Clique Complexes. Proc. of the 2010 annual symposium on Computational geometry (SoCG ’10). ACM, New York, NY, USA, pages 257–266 (2010) CUPS PRODUCTS IN Z2-COHOMOLOGY OF 3D POYHEDRAL COMPLEXES 23 Dept. of Applied Math (I), School of Computer Engineering, University of Seville, Campus Reina Mercedes, C.P. 41012, Seville, Spain E-mail address:[email protected] Pattern Recognition Department, Advanced Technologies Application Center, 7th Avenue #21812 218 and 222, Siboney, Playa, C.P. 12200, Havana City, Cuba E-mail address:[email protected] Department of Mathematics, Millersville University of Pennsylvania, P.O. Box 1002 Millersville, PA 17551-0302, Pennsylvania, USA E-mail address:[email protected]