Computational Homology of Cubical and Permutahedral Complexes

Abstract

Homology is the study of connectivity and "holes" in spaces. The aim of this thesis is to introduce and develop a theory of permutahedral complexes for computations of homology of large data sets and to compare, using efficient implementations, the performance of this theory with that of cubical complexes. We develop practical tools, to be submitted as a GAP package, for computing the homology of n-dimensional Euclidean data sets, where n=1,2,3,4, and certain higher-dimensional data sets. Certain computational advantages of using a permutahedral structure are identified; the notion of a pure B-complex is introduced as a data type for implementing a general class of regular CW-spaces; zig-zag homotopy retractions are introduced as an initial procedure for reducing the number of cells of low-dimensional pure B-complexes with discrete vector field techniques being applied for further reduction; a persistent homology approach to feature recognition in low-dimensional images is illustrated; implementing these algorithms in the GAP system for computational algebra allows for their output to benefit from the system's library of efficient algebraic procedures.