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