Vines and Vineyards by Updating Persistence in Linear Time
In SCG'06: Proceedings of the
22nd Annual ACM
Symposium on Computational Geometry, pages 119-126, New
York, NY, USA, 2006. ACM Press.
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.
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
[7]
David Cohen-Steiner, Herbert Edelsbrunner and John Harer.
Stability of persistence diagrams.
In "Proc. 21st Ann. Sympos. Comput. Geom., 2005", 263-271.
[10]
Herbert Edelsbrunner, David Letscher and Afra Zomorodian.
Topological persistence and simplification.
Discrete Comput. Geom. 28 (2002), 511-533.