Searching combinatorial optimality using graph-based homology information

Abstract

This paper analyses the topological information of a digital object O under a combined combinatorial-algebraic point of view. Working with a topology-preserving cellularization K(O) of the object, algebraic and combinatorial tools are jointly used. The combinatorial entities used here are vector fields, V-paths and directed graphs. In the algebraic side, chain complexes with extra 2-nilpotent operators are considered. By mixing these two perspectives we are able to explore the problems of combinatorial and homological optimality. Combinatorial optimality is understood here as the problem for constructing a discrete gradient vector field (DGVF) in the sense of Discrete Morse Theory, such that it has the least possible number of critical cells. Fixing Z/2Z as field of coefficients, by homological ‘optimality’ we mean the problem of constructing a 2-nilpotent codifferential map ϕ:C∗(K(O))→C∗+1(K(O)) for finite linear combinations of cells in K(O), called homology integral operator. The homology groups associated to the chain complex (C(K(O)),ϕ) are isomorphic to those of (C(K(O)),∂), being ∂ the canonical boundary or differential operator of the cell complex K(O). Relations between these two problems are tackled here by using a type of discrete graphs associated to a homology integral operator, called Homological Spanning Forests (HSF for short). Informally, an HSF for a cell complex can be seen as a kind of combinatorial compressed representation of a homology integral operator. As main result, we refine the heuristic for computing DGVFs based on the iterative Morse complex reduction technique of [1], reducing the search space for an optimal DGVF to an HSF associated to a homology integral operator.