[{"OA_type":"free access","extern":"1","publication_identifier":{"isbn":["9781595933409"]},"publisher":"ACM","date_published":"2006-06-01T00:00:00Z","abstract":[{"lang":"eng","text":"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."}],"_id":"3559","citation":{"ama":"Cohen Steiner D, Edelsbrunner H, Morozov D. Vines and vineyards by updating persistence in linear time. In: <i>Proceedings of the Twenty-Second Annual Symposium on Computational Geometry</i>. ACM; 2006:119-126. doi:<a href=\"https://doi.org/10.1145/1137856.1137877\">10.1145/1137856.1137877</a>","apa":"Cohen Steiner, D., Edelsbrunner, H., &#38; Morozov, D. (2006). Vines and vineyards by updating persistence in linear time. In <i>Proceedings of the twenty-second annual symposium on Computational geometry</i> (pp. 119–126). Sedona, AZ, United States: ACM. <a href=\"https://doi.org/10.1145/1137856.1137877\">https://doi.org/10.1145/1137856.1137877</a>","ista":"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.","ieee":"D. Cohen Steiner, H. Edelsbrunner, and D. Morozov, “Vines and vineyards by updating persistence in linear time,” in <i>Proceedings of the twenty-second annual symposium on Computational geometry</i>, Sedona, AZ, United States, 2006, pp. 119–126.","short":"D. Cohen Steiner, H. Edelsbrunner, D. Morozov, in:, Proceedings of the Twenty-Second Annual Symposium on Computational Geometry, ACM, 2006, pp. 119–126.","chicago":"Cohen Steiner, David, Herbert Edelsbrunner, and Dmitriy Morozov. “Vines and Vineyards by Updating Persistence in Linear Time.” In <i>Proceedings of the Twenty-Second Annual Symposium on Computational Geometry</i>, 119–26. ACM, 2006. <a href=\"https://doi.org/10.1145/1137856.1137877\">https://doi.org/10.1145/1137856.1137877</a>.","mla":"Cohen Steiner, David, et al. “Vines and Vineyards by Updating Persistence in Linear Time.” <i>Proceedings of the Twenty-Second Annual Symposium on Computational Geometry</i>, ACM, 2006, pp. 119–26, doi:<a href=\"https://doi.org/10.1145/1137856.1137877\">10.1145/1137856.1137877</a>."},"title":"Vines and vineyards by updating persistence in linear time","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.","author":[{"first_name":"David","full_name":"Cohen Steiner, David","last_name":"Cohen Steiner"},{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","first_name":"Herbert","full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner"},{"first_name":"Dmitriy","full_name":"Morozov, Dmitriy","last_name":"Morozov"}],"year":"2006","doi":"10.1145/1137856.1137877","day":"01","month":"06","oa_version":"None","publication_status":"published","date_created":"2018-12-11T12:03:58Z","status":"public","conference":{"end_date":"2006-06-07","name":"SCG: Symposium on Computational Geometry","location":"Sedona, AZ, United States","start_date":"2006-06-05"},"article_processing_charge":"No","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","type":"conference","publication":"Proceedings of the twenty-second annual symposium on Computational geometry","page":"119 - 126","publist_id":"2826","language":[{"iso":"eng"}],"date_updated":"2026-08-28T11:06:50Z"},{"month":"06","publication_status":"published","oa_version":"None","date_created":"2018-12-11T12:03:58Z","status":"public","conference":{"name":"SCG: Symposium on Computational Geometry","end_date":"2006-06-07","start_date":"2006-06-05","location":"Sedona, AZ, United States"},"main_file_link":[{"url":"http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.132.4465"}],"article_processing_charge":"No","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","type":"conference","page":"127 - 134","publication":"Proceedings of the twenty-second annual symposium on Computational geometry","publist_id":"2825","date_updated":"2026-08-28T11:01:20Z","language":[{"iso":"eng"}],"OA_type":"closed access","extern":"1","publication_identifier":{"isbn":["9781595933409"]},"publisher":"ACM","date_published":"2006-06-01T00:00:00Z","abstract":[{"text":"We continue the study of topological persistence [5] by investigat- ing the problem of simplifying a function f in a way that removes topological noise as determined by its persistence diagram [2]. To state our results, we call a function g an ε-simplification of another function f if ∥f − g∥∞ ≤ ε, and the persistence diagrams of g are the same as those of f except all points within L1-distance at most ε from the diagonal have been removed. We prove that for func- tions f on a 2-manifold such ε-simplification exists, and we give an algorithm to construct them in the piecewise linear case.","lang":"eng"}],"_id":"3560","citation":{"ista":"Edelsbrunner H, Morozov D, Pascucci V. 2006. Persistence-sensitive simplification of functions on 2-manifolds. Proceedings of the twenty-second annual symposium on Computational geometry. SCG: Symposium on Computational Geometry, 127–134.","ama":"Edelsbrunner H, Morozov D, Pascucci V. Persistence-sensitive simplification of functions on 2-manifolds. In: <i>Proceedings of the Twenty-Second Annual Symposium on Computational Geometry</i>. ACM; 2006:127-134. doi:<a href=\"https://doi.org/10.1145/1137856.1137878\">10.1145/1137856.1137878</a>","apa":"Edelsbrunner, H., Morozov, D., &#38; Pascucci, V. (2006). Persistence-sensitive simplification of functions on 2-manifolds. In <i>Proceedings of the twenty-second annual symposium on Computational geometry</i> (pp. 127–134). Sedona, AZ, United States: ACM. <a href=\"https://doi.org/10.1145/1137856.1137878\">https://doi.org/10.1145/1137856.1137878</a>","short":"H. Edelsbrunner, D. Morozov, V. Pascucci, in:, Proceedings of the Twenty-Second Annual Symposium on Computational Geometry, ACM, 2006, pp. 127–134.","ieee":"H. Edelsbrunner, D. Morozov, and V. Pascucci, “Persistence-sensitive simplification of functions on 2-manifolds,” in <i>Proceedings of the twenty-second annual symposium on Computational geometry</i>, Sedona, AZ, United States, 2006, pp. 127–134.","mla":"Edelsbrunner, Herbert, et al. “Persistence-Sensitive Simplification of Functions on 2-Manifolds.” <i>Proceedings of the Twenty-Second Annual Symposium on Computational Geometry</i>, ACM, 2006, pp. 127–34, doi:<a href=\"https://doi.org/10.1145/1137856.1137878\">10.1145/1137856.1137878</a>.","chicago":"Edelsbrunner, Herbert, Dmitriy Morozov, and Valerio Pascucci. “Persistence-Sensitive Simplification of Functions on 2-Manifolds.” In <i>Proceedings of the Twenty-Second Annual Symposium on Computational Geometry</i>, 127–34. ACM, 2006. <a href=\"https://doi.org/10.1145/1137856.1137878\">https://doi.org/10.1145/1137856.1137878</a>."},"title":"Persistence-sensitive simplification of functions on 2-manifolds","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.","author":[{"first_name":"Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner"},{"full_name":"Morozov, Dmitriy","last_name":"Morozov","first_name":"Dmitriy"},{"full_name":"Pascucci, Valerio","last_name":"Pascucci","first_name":"Valerio"}],"year":"2006","day":"01","doi":"10.1145/1137856.1137878"}]