# Annotating simplices with a homology basis and its applications

O. Busaryev, S. Cabello, C. Chen, T. Dey, Y. Wang, Annotating Simplices with a Homology Basis and Its Applications, ArXiv, 2011.

Download (ext.)

*Report*|

*Published*|

*English*

Author

Department

Abstract

Let K be a simplicial complex and g the rank of its p-th homology group Hp(K) defined with Z2 coefficients. We show that we can compute a basis H of Hp(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 pre-computation of annotations permits 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 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 2-skeleton of K and g the rank of H1(K). Computing an optimal cycle homologous to a given 1-cycle is NP-hard even for surfaces and an algorithm taking 2O(g)nlogn time is known for surfaces. We extend this algorithm to work with arbitrary 2-complexes in O(nω)+2O(g)n2logn time using annotations.

Publishing Year

Date Published

2011-07-19

IST-REx-ID

### Cite this

Busaryev O, Cabello S, Chen C, Dey T, Wang Y.

*Annotating Simplices with a Homology Basis and Its Applications*. ArXiv; 2011.Busaryev, O., Cabello, S., Chen, C., Dey, T., & Wang, Y. (2011).

*Annotating simplices with a homology basis and its applications*. ArXiv.Busaryev, Oleksiy, Sergio Cabello, Chao Chen, Tamal Dey, and Yusu Wang.

*Annotating Simplices with a Homology Basis and Its Applications*. ArXiv, 2011.O. Busaryev, S. Cabello, C. Chen, T. Dey, and Y. Wang,

*Annotating simplices with a homology basis and its applications*. ArXiv, 2011.Busaryev O, Cabello S, Chen C, Dey T, Wang Y. 2011. Annotating simplices with a homology basis and its applications, ArXiv,p.

Busaryev, Oleksiy, et al.

*Annotating Simplices with a Homology Basis and Its Applications*. ArXiv, 2011.### Export

Marked PublicationsOpen Data IST Research Explorer

### Sources

arXiv 1107.3793