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.

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.

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1107.3793

Search this title in

Google Scholar