


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 CCF0830467 and CCF0915996) (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 H_{1}(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 H_{1}(K) for any finite simplicial complex K embedded in Euclidean space. Previous results addressed the case when K is a 2manifold. 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), 166175. 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 = {g_{1}, ... , g_{k}} 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 g_{i} approximates the length of a generator in an optimal set. The results are illustrated in the following image.
Rips Complex We compute a Rips complex R^{2α}(P) out of the given point cloud P. We observe that the rank of the persistence homology group H_{1}^{α,2α}(R(P)) coincides with that of H_{1}(M) for appropriate α. We show that a shortest basis of H_{1}^{α,2α}(R(P)) approximates a shortest basis for H_{1}(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 1skeleton of the simplicial complex K rooted at p, let sp_{T}(q_{1},q_{2}) denote the unique path from q_{1} to q_{2} going through p in T. For a nontree edge e, we define the canonical loop of e with respect to T as the concatenation sp_{T}(p,q_{1}) ο e ο sp_{T}(p,q_{2}). Denote the set of all canonical loops with respect to p as C_{p}. Assuming G_{p} is the greedy set chosen from ∪_{p}C_{p}, we show that the greedy set chosen from ∪_{p}G_{p} is a shortest basis of H_{1}(K). Algorithm Description The algorithm proceeds as follows.
(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 [d_{p+1}] is totally unimodular if and only if H_{p}(L, L_{0}) is torsionfree for all pure subcomplexes L_{0}, L in K of dimension p and p+1 respectively where L_{0} ⊂ 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 NPhard under Z_{2} 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 2cycle in a given homology class for any finite simplicial complex embedded in R^{3}. 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), 221230. arXiv:1001.0338v1[math.AT], 2nd January, 2010. Under Z_{2} coefficients, computing an optimal pcycle c^{*} is NPhard for p ≥ 1. Moreover, various relaxations may still be NPhard. For example, constant factor approximation of c^{*} is NPhard. Even if the rank of the pdimensional homology group is constant, computing c^{*} remains NPhard for p ≥ 2. Fortunately, our result shows that if we switch to the coefficient group Z instead of Z_{2}, 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 ∈ Z^{m} and a real vector of cost coefficients f ∈ R^{n}. Consider the integer linear program 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 pchain c the optimal homologous chain problem is to solve: 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 pchains can be solved in polynomial time. Some examples of computing optimal homology cycles are shown in the image below.
