Measuring and Computing Natural Generators for Homology Groups

C. Chen and D. Freedman

Computational Geometry: Theory and Applications (CGTA), 2010

We develop a method for measuring homology classes. This involves two problems. First, we define the size of a homology class, using ideas from relative homology. Second, we define an optimal basis of a homology group to be the basis whose elements’ size have the minimal sum. We provide a greedy algorithm to compute the optimal basis and measure classes in it. The algorithm runs in O(βn^3 log^2 n) time, where n is the size of the simplicial complex and β is the Betti number of the homology group. Finally, we prove the stability of our result. The algorithm can be adapted to measure any given class.