Annotating Simplices with a Homology Basis and Its Applications

Details Annotating Simplices with a Homology Basis and Its Applications Annotating Simplices with a Homology Basis and Its Applications

2011-07-19

arxiv.org/abs/1107.3793v2

Computer Science

Computational Geometry

Scientific paper

Let $K$ be a simplicial complex and $g$ the rank of its $p$-th homology group $H_p(K)$ defined 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^{\omega})$ time, where $n$ is the size of $K$ and $\omega<2.376$ is a quantity so that two $n\times n$ matrices can be multiplied in $O(n^{\omega})$ 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 $H_1(K)$, we improve the time complexity known for the problem from $O(n^4)$ to $O(n^{\omega}+n^2g^{\omega-1})$. Here $n$ denotes the size of the 2-skeleton of $K$ and $g$ the rank of $H_1(K)$. Computing an optimal cycle homologous to a given 1-cycle is NP-hard even for surfaces and an algorithm taking $O(2^{O(g)}n\log n)$ time is known for surfaces. We extend this algorithm to work with arbitrary 2-complexes in $O(n^{\omega}+2^{O(g)}n^2\log n)$ time using annotations.

Affiliated with

Also associated with

No associations

Rating

Annotating Simplices with a Homology Basis and Its Applications does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Annotating Simplices with a Homology Basis and Its Applications, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Annotating Simplices with a Homology Basis and Its Applications will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-515201