Vines and Vineyards by Updating Persistence in Linear Time

David Cohen-Steiner, Herbert Edelsbrunner, Dmitriy Morozov.
Proceedings of the Annual ACM Symposium on Computational Geometry, pages 119-126, 2006.
PDF SoCG'06
Official ACM version: through ACM portal
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.
PDP = (PRP)(PUP)
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.