Author(s):

Busaryev, Oleksiy; Cabello, Sergio; Chen, Chao; Dey, Tamal K; Wang, Yusu

Title: 
Annotating simplices with a homology basis and its applications

Affiliation 
IST Austria 
Abstract: 
Let K be a simplicial complex and g the rank of its pth homology group Hp(K) defined with Z2 coefficients. We show that we can compute a basis H of Hp(K) and annotate each psimplex of K with a binary vector of length g with the following property: the annotations, summed over all psimplices in any pcycle 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 precomputation of annotations permits answering queries about the independence or the triviality of pcycles efficiently.
Using annotations of edges in 2complexes, we derive better algorithms for computing optimal basis and optimal homologous cycles in 1dimensional homology. Specifically, for computing an optimal basis of H1(K), we improve the time complexity known for the problem from O(n4) to O(nω+n2gω−1). Here n denotes the size of the 2skeleton of K and g the rank of H1(K). Computing an optimal cycle homologous to a given 1cycle is NPhard even for surfaces and an algorithm taking 2O(g)nlogn time is known for surfaces. We extend this algorithm to work with arbitrary 2complexes in O(nω)+2O(g)n2logn time using annotations.

Publication Title:

CoRR: Computing Research Repository

Issue 
abs/1107.3793

Publisher:

ArXiv

Date Published:

20110719

URL: 

Open access: 
yes (repository) 