[{"extern":1,"abstract":[{"lang":"eng"}],"publist_id":"2826","type":"conference","date_created":"2018-12-11T12:03:58Z","dini_type":"doc-type:conferenceObject","date_updated":"2021-01-12T07:44:18Z","author":[{"first_name":"David","last_name":"Cohen Steiner"},{"first_name":"Herbert","last_name":"Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833"},{"first_name":"Dmitriy","last_name":"Morozov"}],"status":"public","publication_status":"published","_id":"3559","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.","month":"06","day":"01","uri_base":"https://research-explorer.ista.ac.at","dc":{"title":["Vines and vineyards by updating persistence in linear time"],"publisher":["ACM"],"relation":["info:eu-repo/semantics/altIdentifier/doi/10.1145/1137856.1137877"],"rights":["info:eu-repo/semantics/closedAccess"],"source":["Cohen Steiner D, Edelsbrunner H, Morozov D. Vines and vineyards by updating persistence in linear time. In: ACM; 2006:119-126. doi:10.1145/1137856.1137877"],"date":["2006"],"description":["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."],"identifier":["https://research-explorer.ista.ac.at/record/3559"],"type":["info:eu-repo/semantics/conferenceObject","doc-type:conferenceObject","text","http://purl.org/coar/resource_type/c_5794"],"creator":["Cohen-Steiner, David","Herbert Edelsbrunner","Morozov, Dmitriy"]},"conference":{"name":"SCG: Symposium on Computational Geometry"},"date_published":"2006-06-01T00:00:00Z","quality_controlled":0,"page":"119 - 126","citation":{"chicago":"Cohen Steiner, David, Herbert Edelsbrunner, and Dmitriy Morozov. “Vines and Vineyards by Updating Persistence in Linear Time,” 119–26. ACM, 2006. https://doi.org/10.1145/1137856.1137877.","short":"D. Cohen Steiner, H. Edelsbrunner, D. Morozov, in:, ACM, 2006, pp. 119–126.","mla":"Cohen Steiner, David, et al. Vines and Vineyards by Updating Persistence in Linear Time. ACM, 2006, pp. 119–26, doi:10.1145/1137856.1137877.","ieee":"D. Cohen Steiner, H. Edelsbrunner, and D. Morozov, “Vines and vineyards by updating persistence in linear time,” presented at the SCG: Symposium on Computational Geometry, 2006, pp. 119–126.","apa":"Cohen Steiner, D., Edelsbrunner, H., & Morozov, D. (2006). Vines and vineyards by updating persistence in linear time (pp. 119–126). Presented at the SCG: Symposium on Computational Geometry, ACM. https://doi.org/10.1145/1137856.1137877","ista":"Cohen Steiner D, Edelsbrunner H, Morozov D. 2006. Vines and vineyards by updating persistence in linear time. SCG: Symposium on Computational Geometry, 119–126."}}]