[{"publisher":"ACM","publication_identifier":{"isbn":["9781595933409"]},"date_published":"2006-06-01T00:00:00Z","_id":"3559","citation":{"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>.","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>.","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.","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.","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>"},"abstract":[{"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.","lang":"eng"}],"title":"Vines and vineyards by updating persistence in linear time","author":[{"full_name":"Cohen Steiner, David","last_name":"Cohen Steiner","first_name":"David"},{"last_name":"Edelsbrunner","orcid":"0000-0002-9823-6833","full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","first_name":"Herbert"},{"first_name":"Dmitriy","full_name":"Morozov, Dmitriy","last_name":"Morozov"}],"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.","year":"2006","day":"01","doi":"10.1145/1137856.1137877","OA_type":"free access","extern":"1","status":"public","article_processing_charge":"No","conference":{"name":"SCG: Symposium on Computational Geometry","end_date":"2006-06-07","start_date":"2006-06-05","location":"Sedona, AZ, United States"},"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","type":"conference","publication":"Proceedings of the twenty-second annual symposium on Computational geometry","publist_id":"2826","page":"119 - 126","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"},{"date_published":"2006-06-01T00:00:00Z","publisher":"ACM","publication_identifier":{"isbn":["9781595933409"]},"title":"Persistence-sensitive simplification of functions on 2-manifolds","citation":{"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.","short":"H. Edelsbrunner, D. Morozov, V. Pascucci, in:, Proceedings of the Twenty-Second Annual Symposium on Computational Geometry, ACM, 2006, pp. 127–134.","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.","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>","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>","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>."},"_id":"3560","abstract":[{"lang":"eng","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."}],"year":"2006","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":[{"last_name":"Edelsbrunner","orcid":"0000-0002-9823-6833","full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","first_name":"Herbert"},{"first_name":"Dmitriy","last_name":"Morozov","full_name":"Morozov, Dmitriy"},{"last_name":"Pascucci","full_name":"Pascucci, Valerio","first_name":"Valerio"}],"doi":"10.1145/1137856.1137878","day":"01","extern":"1","OA_type":"closed access","status":"public","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","conference":{"location":"Sedona, AZ, United States","start_date":"2006-06-05","end_date":"2006-06-07","name":"SCG: Symposium on Computational Geometry"},"article_processing_charge":"No","main_file_link":[{"url":"http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.132.4465"}],"publication":"Proceedings of the twenty-second annual symposium on Computational geometry","publist_id":"2825","page":"127 - 134","type":"conference","language":[{"iso":"eng"}],"date_updated":"2026-08-28T11:01:20Z","month":"06","oa_version":"None","publication_status":"published","date_created":"2018-12-11T12:03:58Z"}]