The DOI matches its Crossref record; 4 of the 4 references it cites were found in a registry or an index.
Vines and vineyards by updating persistence in linear time
Abstract
Persistent homology is the mathematical core of recent work on shape, including reconstruction, recognition, and matching. Its pertinent 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 analysis 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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Topological Persistence and Simplification
Edelsbrunner, Letscher, & Zomorodian (2002) · Discrete & Computational Geometry · doi:10.1007/s00454-002-2885-2 · Cited by 1,779
Zomorodian, A., & Carlsson, G. (2005) · Discrete & Computational Geometry · doi:10.1007/s00454-004-1146-y · Cited by 1,591
Stability of persistence diagrams
Cohen-Steiner, D., Edelsbrunner, H., & Harer, J. (2005) · Proceedings of the twenty-first annual symposium on Computational geometry · doi:10.1145/1064092.1064133 · Cited by 251
Self-citationPersistence barcodes for shapes
Carlsson, G., Zomorodian, A., Collins, A., & Guibas, L. (2004) · Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing · doi:10.1145/1057432.1057449 · Cited by 133
Cited by
Proximity of persistence modules and their diagrams
Chazal, F., Cohen-Steiner, D., Glisse, M., Guibas, L. J., & Oudot, S. Y. (2009) · Proceedings of the twenty-fifth annual symposium on Computational geometry · doi:10.1145/1542362.1542407 · Cited by 404
Self-citationThe Structure and Stability of Persistence Modules
Chazal, F., de Silva, V., Glisse, M., & Oudot, S. (2016) · SpringerBriefs in Mathematics · doi:10.1007/978-3-319-42545-0 · Cited by 393
Zigzag persistent homology and real-valued functions
Carlsson, G., de Silva, V., & Morozov, D. (2009) · Proceedings of the twenty-fifth annual symposium on Computational geometry · doi:10.1145/1542362.1542408 · Cited by 272
Self-citationA spectral sequence for parallelized persistence
Lipsky, D., Skraba, P., & Vejdemo-Johansson, M. (2011) · arXiv · doi:10.48550/arxiv.1112.1245 · Cited by 22
Metadata
- Authors
- Cohen-Steiner, D., Edelsbrunner, H., & Morozov, D.
- Venue
- Proceedings of the twenty-second annual symposium on Computational geometry
- Publisher
- ACM
- Published
- 2006-06-05
- Pages
- 119-126
- OpenAlex
- W2009940349
- Cited by
- 239
- References
- 4
- FWCI
- 10.38
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Vines and vineyards by updating persistence in linear time. https://app.cochat.ai/papers/10.1145/1137856.1137877
- The paper
- 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. https://doi.org/10.1145/1137856.1137877
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.