Workshop on Topology: Identifying Order in Complex Systems

Computation of cycles representing classes of homology groups is a fundamental problem arising in applications such as parameterization, feature identification, topology simplification, and data analysis. Variations of the classical Smith Normal Form algorithm and the recently developed persistence algorithm do compute representative cycles of a homology basis for a simplicial complex, but they remain oblivious to the input geometry. Some recent research in computational topology has addressed the problems of computing homology cycles that are optimal with respect to a given metric. In this talk, we concentrate on two such developments: (i) Computing an optimal basis for one dimensional homology of a simplicial complex and using it to approximate such a basis for a smooth manifold from its point data; (ii) Computing an optimal cycle homologous to a given cycle in a simplicial complex. We provide efficient algorithms with their guarantees for (i) and show that classical Linear Programs can solve (ii) for some interesting cases even though the general problem is NP-hard.