Annotating Simplices with a Homology Basis and Its Applications

摘要

Let K be a simplicial complex and g the rank of its p-th homology group H_p(K) denned with Z_2 coefficients. We show that we can compute a basis H of H_p(K) and annotate each p-simplex of K with a binary vector of length g with the following property: the annotations, summed over all p-simplices in any p-cycle z, provide the coordinate vector of the homology class [z] in the basis H. The basis and the annotations for all simplices can be computed in O(n~ω) time, where n is the size of K and ω < 2.376 is a quantity so that two n × n matrices can be multiplied in O(n~ω) time. The precomputed annotations permit answering queries about the independence or the triviality of p-cycles efficiently. Using annotations of edges in 2-complexes, we derive better algorithms for computing optimal basis and optimal homologous cycles in 1 - dimensional homology. Specifically, for computing an optimal basis of H_1 (K), we improve the previously known time complexity from O(n~4) to O(n~ω + n~2g~(ω-1)). Here n denotes the size of the 2-skeleton of K and g the rank of H_1 (AC). Computing an optimal cycle homologous to a given 1-cycle is NP-hard even for surfaces and an algorithm taking 2~(O(g))n log n time is known for surfaces. We extend this algorithm to work with arbitrary 2-complexes in O(n~ω) + 2~(O(g))n~2 logn time using annotations.