Vines and vineyards by updating persistence in linear time
Cohen Steiner D, Edelsbrunner H, Morozov D. 2006. Vines and vineyards by updating persistence in linear time. Proceedings of the twenty-second annual symposium on Computational geometry. SCG: Symposium on Computational Geometry, 119–126.
Download
No fulltext has been uploaded. References only!
Conference Paper
| Published
| English
Author
Cohen Steiner, David;
Edelsbrunner, HerbertISTA 
;
Morozov, Dmitriy
;
Morozov, DmitriyAbstract
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.
Publishing Year
Date Published
2006-06-01
Proceedings Title
Proceedings of the twenty-second annual symposium on Computational geometry
Publisher
ACM
Acknowledgement
Partially supported by NSF under grant CCR- 00-86013, by DARPA under grant HR0011-05-1-0007, and by the Lawrence Livermore National Laboratory under grant B543154.
Page
119 - 126
Conference
SCG: Symposium on Computational Geometry
Conference Location
Sedona, AZ, United States
Conference Date
2006-06-05 – 2006-06-07
ISBN
IST-REx-ID
Cite this
Cohen Steiner D, Edelsbrunner H, Morozov D. Vines and vineyards by updating persistence in linear time. In: Proceedings of the Twenty-Second Annual Symposium on Computational Geometry. ACM; 2006:119-126. doi:10.1145/1137856.1137877
Cohen Steiner, D., Edelsbrunner, H., & Morozov, D. (2006). Vines and vineyards by updating persistence in linear time. In Proceedings of the twenty-second annual symposium on Computational geometry (pp. 119–126). Sedona, AZ, United States: ACM. https://doi.org/10.1145/1137856.1137877
Cohen Steiner, David, Herbert Edelsbrunner, and Dmitriy Morozov. “Vines and Vineyards by Updating Persistence in Linear Time.” In Proceedings of the Twenty-Second Annual Symposium on Computational Geometry, 119–26. ACM, 2006. https://doi.org/10.1145/1137856.1137877.
D. Cohen Steiner, H. Edelsbrunner, and D. Morozov, “Vines and vineyards by updating persistence in linear time,” in Proceedings of the twenty-second annual symposium on Computational geometry, Sedona, AZ, United States, 2006, pp. 119–126.
Cohen Steiner D, Edelsbrunner H, Morozov D. 2006. Vines and vineyards by updating persistence in linear time. Proceedings of the twenty-second annual symposium on Computational geometry. SCG: Symposium on Computational Geometry, 119–126.
Cohen Steiner, David, et al. “Vines and Vineyards by Updating Persistence in Linear Time.” Proceedings of the Twenty-Second Annual Symposium on Computational Geometry, ACM, 2006, pp. 119–26, doi:10.1145/1137856.1137877.
Google Scholar
ISBN Search