Vines and vineyards by updating persistence in linear time
Cohen-Steiner, David
Herbert Edelsbrunner
Morozov, Dmitriy
Persistent homology is the mathematical core of recent work on shape, including reconstruction, recognition, and matching. Its per- tinent 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 anal- ysis 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.
ACM
2006
info:eu-repo/semantics/conferenceObject
doc-type:conferenceObject
text
https://research-explorer.app.ist.ac.at/record/3559
Cohen Steiner D, Edelsbrunner H, Morozov D. Vines and vineyards by updating persistence in linear time. In: ACM; 2006:119-126. doi:<a href="https://doi.org/10.1145/1137856.1137877">10.1145/1137856.1137877</a>
info:eu-repo/semantics/altIdentifier/doi/10.1145/1137856.1137877
info:eu-repo/semantics/closedAccess