Project topics and materials
Get Complete Project Material File(s) Now! »
Previous Works
This chapter somehow creates a new problem instead of solving an existing one. This justifies the shortness of this section. Discrete Morse theory was introduced in [49, 50]. It was then reformu-lated in terms of matchings in [15, 80]. Discrete Morse theory is often used for simplifying a complex in order to accelerate the computation of its ho-mology. Thus, it can be seen as an optimization problem, in which one wants to find a discrete gradient vector field (a matching in the Hasse dia-gram of a CW complex) with as many edges as possible. It was proved that this is an NP-hard problem (see [83, 73]). Nevertheless, there has been an extensive research on this optimization problem without aiming at finding a perfect solution in the general case, such as in [83, 73, 46, 91]. There has been a parallel and successful research about simplifying a CW complex in [78, 94, 95]. These works were recently related to discrete Morse theory in [66], which states that reductions and coreductions are particular strategies for establishing a discrete gradient vector field.
CW Complex
Computational topology needs topological spaces that can be described through a finite representation. A rigorous presentation of CW complexes would be too long for this chapter, so we give an intuitive introduction and we let the reader satisfy its curiosity by consulting [86]. A CW complex, or cell complex, is a collection of closed unit balls (up to homeomorphism) of different dimensions, called cells, that are “glued” together by their boundary: every cell of dimension q ≥ 1 (q-cell) has a map from its boundary to the lower dimensional cells. A q-cell σ is denoted σ (q) whenever its dimension is not clear from the context. We are certainly interested in the case where the number of cells is finite. To be honest, we only use the notion of CW complex for comprehending simplicial complexes, cubical complexes or even polyhedra [110, §1.1]. We could have chosen to work with S-complexes [94] but we have preferred the CW complexes, as in [39]. We say that a cell σ is a face of another one τ if it is contained in its boundary. A special case is when they have consecutive dimensions, in which we say that it is a primary face and we write σ < τ
Given a CW complex, we can define its Hasse diagram. It is a directed graph whose vertices represent the cells and whose arrows go from each cell to its primary faces. In this chapter we usually do not make the dis-tinction between the vertices and the cells they represent, so we mix these terms.
Homology of a CW complex
The definition of the homology groups of a CW complex is similar to the case of simplicial or cubical complexes. Let R be a ring. We usually consider R to be Z2 = Z/2Z or Z. We say that an element of R is a unit if it is invertible for the multiplication. We denote by R∗ the set of the units of R. For instance, Z∗2 = {1} and Z∗ = {−1, 1}. Given a CW complex K, we define its associated chain complex C(K) as follows:
• Cq is the free R-module generated by the q-dimensional cells of K.
• dq gives the “algebraic” boundary, which is the linear operator that maps every cell to the sum of its primary faces with specific coeffi-cients. These coefficients, which are not unique, can be computed with the algorithm present in [39, §3.1]. We will usually use the term complex for the CW complex or its asso-ciated chain complex. This chain complex can be seen as a sequence of matrices that express the relation of inclusion between the cells. However, note that not every chain complex is the chain complex associated to a CW complex.
The elements of the chain group Cq, which are formal linear combina-tions of cells, are called q-chains. If x = i∈I λiσi then x, σi := λi denotes the coefficient of σi in the chain x.
Homological Information
Given the definition of the homology groups, we could ask ourselves how much information we want to obtain. If we want to use homology as a topo-logical invariant, it should be enough to know its Euler-Poincaré character-istic or, more generally, its Betti numbers and torsion coefficients. More-over, if we want to use homology to better understand the shape of the complex, we could be interested in knowing a representative of each class of homology that is a generator. These representatives, which we directly call homology generators, are not unique at all, and it is an interesting and ill-defined problem to find a set of well-shaped generators. Furthermore, we can decompose a given cycle onto the computed homology generators. Since not all works in computational homology try to obtain the same information, we propose the following classification of homological infor-mation:
Level 0 : The Euler-Poincaré characteristic [67, p. 146].
Level 1 : The Betti numbers. They are the rank of the free part of the ho-mology groups.
Level 2 : Invariant factor decomposition of the homology groups.
Level 3 : Homology group with generators: Z [z1] × · · · × Z zβQ ×Z [t1] /λ1Z [c1]× Z/ [t2] λ2Z [c2] × · · ·
Level 4 : Homology group with generators and decomposition of cycles.
Each level of homological information can be trivially deduced from the upper ones. We have decided to start from level 0 since the Euler-Poincaré characteristic is the easiest computable homological information. Persistent homology usually works at level 1 (in each complex of the filtration), which is equivalent to level 2 because the ground ring considered is usually a field; Munkres’ original theorem/method arrives to level 2 and the modified-SNF [102] reaches the third level. Effective homology theory arrives to the fourth level whenever we have a perfect reduction (see Section 2.3.4), since for a given cycle x ∈ ker(dq), f (x) decomposes it onto a linear combination of generators. This classification could be extended with (co)homology operations, the cohomology ring or even the homotopy groups.
Discrete Morse Theory
Discrete Morse theory was introduced by Robin Forman as a discretization of the Morse theory [50]. One of the main ideas is to obtain some homo-logical information by means of a function defined on a CW complex. This function is equivalent to a discrete gradient vector field and we rather use this notion. A discrete vector field (DVF) on a CW complex is a matching on its Hasse diagram, that is a collection of edges such that no two of them have a com-mon vertex. From a Hasse diagram and a discrete vector field we can de-fine a Morse graph: it is a graph similar to the Hasse diagram except for the arrows contained in the matching, which are reversed. These arrows are called integral arrows, and the others, differential arrows. Given a DVF over a CW complex K, its cells can be partitioned into the following classes: Primary (P) The cells having an out-going integral arrow. Secondary (S) The cells having an in-going integral arrow. Critical (C) The cells not incident to any integral arrow. Since the DVF is a matching, it is immediate that K = P ⊔ S ⊔ C. This notation is inspired by [91, Def. 1], but this classification was previously introduced in [66, Def. 3.1] and [12, §5] with a different notation. A V-path is a path on the Morse graph that alternates between integral and differential arrows. Its length is the number of integral arrows con-tained. A discrete gradient vector field (DGVF) is a discrete vector field that does not contain any closed V-path. As mentioned above, a critical vertex (or critical cell) is a vertex that is not paired by the matching. Figure 3.1 shows the usual representation of a DGVF over a cubical complex.
One of the main results of discrete Morse theory is that the number of critical q-cells is greater than or equal to the q-th Betti number. When they are equal, we say that the DGVF is perfect. An optimal DGVF contains the least possible number of critical cells. Every perfect DGVF is obviously optimal, but the converse is false. Therefore, a DGVF gives an estimation of the Betti numbers without using any algebraic method. We could say that it is a “combinatorial” tool.
Table of contents :
Abstract
French Extended Abstract – Résumé étendu
Spanish Extended Abstract – Resumen extendido
Acknowledgements
1 Introduction
1.1 Overview
1.2 How to read this dissertation
2 Common Background
2.1 General Topology
2.2 Algebraic Topology
2.2.1 Homotopy
2.2.2 Homology
2.3 Computational topology
2.3.1 Homotopy
2.3.2 Simplicial homology
2.3.3 Cubical homology
2.3.4 Effective Homology
2.3.5 Persistent homology
2.4 Digital Geometry
3 The Homological Discrete Vector Field
3.1 Introduction
3.2 PreviousWorks
3.3 Preliminaries
3.3.1 CW Complex
3.3.2 Homology of a CW complex
3.3.3 Homological Information
3.3.4 Discrete Morse Theory
3.3.5 Some Matrix Properties
3.4 Motivation
3.5 Introducing the HDVF
3.6 Computing a HDVF
3.6.1 Computing the Reduced Complex
3.6.2 Computing also the reduction
3.6.3 Some questions about the algorithm
3.6.4 Another algorithm for computing a HDVF
3.7 Deforming a HDVF
3.7.1 Basic Operations
3.7.2 Delineating (co)homology generators
3.7.3 Connectivity between HDVFs
3.8 Relation with other Methods in Computational Homology .
3.8.1 Iterated Morse decomposition
3.8.2 The Smith normal form
3.8.3 Persistent homology
3.9 Experimental Complexity
3.10 Conclusion and future work
4 Fast Computation of Betti Numbers on Three-Dimensional Cubical Complexes
4.1 Introduction
4.2 The Iterative Algorithm
4.3 The Recursive Algorithm
4.4 Results
4.5 Conclusion
5 Measuring Holes
5.1 Introduction
5.2 The measures
5.2.1 On the computation of the measures
5.2.2 The robustness of the measures
5.3 Thickness and breadth balls
5.4 Small generators
5.4.1 Homology generators
5.4.2 Cohomology generators
5.5 Opening or closing holes
5.5.1 Opening a hole
5.5.2 Closing a hole
5.5.3 We want voxels, not cubes
5.6 Conclusion and future works
6 Conclusion
6.1 General conclusion
6.1.1 Homological Discrete Vector Field
6.1.2 Fast Computation of Betti Numbers on Three-Dimensional Cubical Complexes
6.1.3 Measuring Holes
6.2 Other works
6.2.1 Cellular skeletons
6.2.2 Opening holes in discrete objects
