Vines and vineyards by updating persistence in linear time

ABSTRACT

Persistent homology is the mathematical core of recent work on shape, including reconstruction, recognition, and matching. Its pertinent information is encapsulated by a pairing of the critical values of a function, visualized by points forming a diagram in the plane. The original algorithm in [10] computes the pairs from an ordering of the simplices in a triangulation and takes worst-case time cubic in the number of simplices. The main result of this paper is an algorithm that maintains the pairing in worst-case linear time per transposition in the ordering. A side-effect of the algorithm's analysis is an elementary proof of the stability of persistence diagrams [7] in the special case of piecewise-linear functions. We use the algorithm to compute 1-parameter families of diagrams which we apply to the study of protein folding trajectories.

REFERENCES

• 1: P. K. Agarwal, H. Edelsbrunner, J. Harer and Y. Wang. Extreme elevation on a 2-manifold. "Proc. 20th Ann. Sympos. Comput. Geom., 2004", 357--365.
• 2: M. d'Amico, P. Frosini and C. Landi. Optimal matching between reduced size functions. Tech. Rept. 35, DISMI, Univ. degli Studi di Modena e Reggio Emilia, Italy, 2003.
• 3: M. d'Amico, P. Frosini and C. Landi. Natural pseudo-distance and optimal matching between reduced size functions. Tech. Rept. 66, DISMI, Univ. degli Studi di Modena e Reggio Emilia, Italy, 2005.
• 4: T. Banchoff. Critical points and curvature for embedded polyhedra. J. Diff. Geom. 1 (1967), 245--256.
• 5: Gunnar Carlsson , Afra Zomorodian , Anne Collins , Leonidas Guibas, Persistence barcodes for shapes, Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing, July 08-10, 2004, Nice, France [doi>10.1145/1057432.1057449]
• 6: Afra Zomorodian , Gunnar Carlsson, Computing persistent homology, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA [doi>10.1145/997817.997870]
• 7: David Cohen-Steiner , Herbert Edelsbrunner , John Harer, Stability of persistence diagrams, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy [doi>10.1145/1064092.1064133]
• 8: David Cohen-Steiner , Herbert Edelsbrunner, Inequalities for the curvature of curves and surfaces, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy [doi>10.1145/1064092.1064134]
• 9: V. de Silva and G. Carlsson. Topological estimation using witness complexes. "Proc. Sympos. Point-Based Graphics, 2004", 157--166.
• 10: H. Edelsbrunner, D. Letscher and A. Zomorodian. Topological persistence and simplification. {Discrete Comput. Geom. 28 (2002), 511--533.
• 11: N. Gelfand, N. J. Mitra, L. J. Guibas and H. Pottmann. Robust global alignment. In "Proc. 3rd Ann. Eurographics Sympos. Geom. Process., 2005", 197--206.
• 12: D. Huber and M. Hebert. Fully automatic registration of multiple 3D data sets. Image Vision Comput. 21 (2003), 637--650.
• 13: J. McCleary. User's Guide to Spectral Sequences. Publish or Perish, Wilmington, Delaware, 1985.
• 14: J. Milnor. Morse Theory. Princeton Univ. Press, New Jersey, 1963.
• 15: J. R. Munkres. Elements of Algebraic Topology. Addison-Wesley, Redwood City, California, 1984.
• 16: Y. M. Rhee, E. J. Sorin, G. Jayachandran, E. Lindahl and V. Pande. Simulations of the role of water in the protein-folding mechanism. Proc. Natl. Acad. Sci. 101 (2004), 6456--6461.
• 17: D. Russell and L. J. Guibas. Exploring protein folding trajectories using geometric spanners. "Proc. Pacific Sympos. Biocomput., 2005", 40--51.
• 18: Y. Wang, P. K. Agarwal, P. Brown, H. Edelsbrunner and J. Rudolph. Coarse and reliable geometric alignment for protein docking. "Proc. Pacific Sympos. Biocomput., 2005", 65--75.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Counting problems

General Terms:
Algorithms, Theory

Keywords:
combinatorial topology, dynamic algorithms, folding trajectories, implementation, persistent homology groups, stability