Research on Computing (Optimal) Homology Cycles
Home

People

Research

Publications




In this reserach we design algorithms to compute cycles that represent homology classes.  The challenge is to incorporate geometry in this computation.  The cycles/loops not only should be topologically correct but also should be `short' or optimal. There are three main results:

1. Computing Handle and Tunnel loops on a surface: Here input is a triangulated surface or a volume in 3d. Output is a set of loops called handle and tunnel loops. Go here to know the details. HanTun software is based on this result

2. Computing loops in a shortest homology basis:  Here we consider computing a set of loops that represent a shortest basis of the first homology group. The input could be a simplicial complex (more general than a surface) or a point cloud data of a manifold. See below for details.  ShortLoop software is based on this result.

3. Computing optimal homologous cycle: Here input is a cycle (any dimensional, not necessarily one dimensional) in a simplicial complex. The output is a shortest (optimal) cycle in the same homology class under integer coefficient. See below for details.


(This research is supported by NSF grants CCF-0830467 and CCF-0915996)

./circle23_blue.gif  (2) Approximating Loops in a Shortest Homology Basis from Point Data/simplicial complex

Abstract. Inference of topological and geometric attributes of a hidden manifold from its point data is a fundamental problem arising in many scientific studies and engineering applications. In this work we present an algorithm to compute a set of loops from a point data which approximates a shortest basis of the one dimensional homology group H1(M) of the sampled manifold M. Previous results addressed the issue of computing the rank of the homology groups from point data, but there is no result on approximating the shortest basis of a manifold from its point sample. In arriving our result, we also present a polynomial time algorithm for computing a shortest basis of H1(K) for any finite simplicial complex K embedded in Euclidean space.  Previous results addressed the case when K is a 2-manifold. We do not have any restriction on K other than it being finite.

Paper: T. K. Dey, J. Sun, and Y. Wang. Approximating loops in a shortest homology basis from point data. Proc. 26th Annu. Sympos. Comput. Geom. (SOCG 2010), 166--175. arXiv:0909.5654v1[cs.CG], 30th September 2009.

We present an algorithm that, given a smooth manifold without boundary M, computes a set of homology loops G = {g1, ... , gk} from an ε-sample P of M and a parameter α > 0 whose total length is within a factor (dependent on ε and α ) of the total length of a shortest set of generators in M. In fact, our proof implies a stronger result, where the length of each gi approximates the length of a generator in an optimal set. The results are illustrated in the following image.

Approximating shortest homology basis on Eight. From left to right: input point cloud, Rips complex, computed homology basis.


Rips Complex
We compute a Rips complex R2α(P) out of the given point cloud P. We observe that the rank of the persistence homology group H1α,2α(R(P)) coincides with that of H1(M) for appropriate α. We show that a shortest basis of H1α,2α(R(P)) approximates a shortest basis for H1(M).  This shortest basis can be computed from the Rips complex. For this we devise an algorithm to compute the loops in a shortest basis for any finite simplicial complex K.

Candidate Loops
We collect all tight loops (loops that contain a shortest path between every pair of points in the loop) by considering all  canonical loops defined as follows. Given a shortest path tree in 1-skeleton of the simplicial complex K rooted at p, let spT(q1,q2) denote the unique path from q1 to q2 going through p  in T. For a non-tree edge e, we define the canonical loop of e with respect to T as the concatenation spT(p,q1) ο e ο spT(p,q2). Denote the set of all canonical loops with respect to p as Cp. Assuming Gp is the greedy set chosen from ∪pCp, we show that the greedy set chosen from ∪pGp is a shortest basis of H1(K).

Algorithm Description
The algorithm proceeds as follows.
  1. For each p in P, compute the greedy set Gp of canonical loops (we propose a novel use of persistence algorithm here).
  2. Sort all the loops in ∪pGp in the increasing order.
  3. Set G to be the empty set.
  4. Traversing all the loops in the sorted order, we add a loop g to G if g is independent of all loops in G; otherwise proceed.
We determine if the loop is independent of all loops in G by using a sealing technique and persistence.

./circle23_blue.gif (3) Optimal homologous cycles, total unimodularity, and linear programming.

Abstract. Given a simplicial complex with weights on its simplices, and a nontrivial cycle on it, we are interested in finding the cycle with minimal weight which is homologous to the given one. Assuming that the homology is defined with integer (Z) coefficients, we show the following: For a finite simplicial complex K of dimension greater than p, the boundary matrix [dp+1] is totally unimodular if and only if Hp(L, L0) is torsion-free for all pure subcomplexes L0, L in K of dimension p and p+1 respectively where L0 ⊂ L. Because of the total unimodularity of the boundary matrix, we can solve the optimization problem, which is inherently an integer programming problem, as a linear program and obtain integer solution. Thus the problem of finding optimal cycles in a given homology class can be solved in polynomial time. This result is surprising in the backdrop of a recent result which says that the problem is NP-hard under Z2 coefficients which, being a field, is in general easier to deal with. One consequence of our result, among others, is that one can compute in polynomial time an optimal 2-cycle in a given homology class for any finite simplicial complex embedded in R3. Our optimization approach can also be used for various related problems, such as finding an optimal chain homologous to a given one when they are not cycles.

Paper: T. K. Dey, A. Hirani, and B. Krishnamoorthy. Optimal homologous cycles, total unimodularity, and linear programming. 42nd ACM Sympos. Comput. Theory (STOC 2010), 221--230. arXiv:1001.0338v1[math.AT], 2nd January, 2010.

Under Z2 coefficients, computing an optimal p-cycle c* is NP-hard for p ≥ 1. Moreover, various relaxations may still be NP-hard. For example, constant factor approximation of c* is NP-hard. Even if the rank of the p-dimensional homology group is constant, computing c* remains NP-hard for p ≥ 2. Fortunately, our result shows that if we switch to the coefficient group Z instead of Z2, the problem becomes polynomial time solvable for a fairly large class of spaces when casted as a linear optimization problem.

Total unimodularity
A matrix is totally unimodular if the determinant of each square submatrix is 0, 1, or -1. The significance of total unimodularity in our setting is due to the following result. Consider an integral vector b ∈ Zm and a real vector of cost coefficients f ∈ Rn. Consider the integer linear program

min fTx subject to Ax = b; x ≥ 0 and x ∈ Zn

Let A be a totally unimodular matrix. Then the integer linear program above can be solved in time polynomial in the dimensions of A.

Optimal homologous chains and linear programming
Assume that the number of p- and (p + 1)-simplices in K is m and n respectively and let W be a diagonal m x m matrix. Given an integer valued p-chain c the optimal homologous chain problem is to solve:

minx,y||Wx||1 such that x = c + [∂p+1]y, and x ∈ Zm, y ∈ Zn

If the boundary matrix [∂p+1] of a finite simplicial complex of dimension greater than p is totally unimodular, the optimal homologous chain problem above for p-chains can be solved in polynomial time.

Some examples of computing optimal homology cycles are shown in the image below.

Computing optimal homology cycles on Eight, Rocket Arm, Elk, Genus3 and Pig models. Initial cycles computed by the persistence algorithm are shown in red, optimal cycles are shown in green.