---
_id: '2939'
abstract:
- lang: eng
  text: In this paper, we present the first output-sensitive algorithm to compute
    the persistence diagram of a filtered simplicial complex. For any Γ > 0, it
    returns only those homology classes with persistence at least Γ. Instead of the
    classical reduction via column operations, our algorithm performs rank computations
    on submatrices of the boundary matrix. For an arbitrary constant δ ∈ (0, 1), the
    running time is O (C (1 - δ) Γ R d (n) log n), where C (1 - δ) Γ is the number
    of homology classes with persistence at least (1 - δ) Γ, n is the total number
    of simplices in the complex, d its dimension, and R d (n) is the complexity of
    computing the rank of an n × n matrix with O (d n) nonzero entries. Depending
    on the choice of the rank algorithm, this yields a deterministic O (C (1 - δ)
    Γ n 2.376) algorithm, an O (C (1 - δ) Γ n 2.28) Las-Vegas algorithm, or an O (C
    (1 - δ) Γ n 2 + ε{lunate}) Monte-Carlo algorithm for an arbitrary ε{lunate} >
    0. The space complexity of the Monte-Carlo version is bounded by O (d n) = O (n
    log n).
acknowledgement: The authors thank Herbert Edelsbrunner for many helpful discussions
  and suggestions. Moreover, they are grateful for the careful reviews that helped
  to improve the quality of the paper.
article_processing_charge: No
author:
- first_name: Chao
  full_name: Chen, Chao
  id: 3E92416E-F248-11E8-B48F-1D18A9856A87
  last_name: Chen
- first_name: Michael
  full_name: Kerber, Michael
  id: 36E4574A-F248-11E8-B48F-1D18A9856A87
  last_name: Kerber
  orcid: 0000-0002-8030-9299
citation:
  ama: 'Chen C, Kerber M. An output sensitive algorithm for persistent homology. <i>Computational
    Geometry: Theory and Applications</i>. 2013;46(4):435-447. doi:<a href="https://doi.org/10.1016/j.comgeo.2012.02.010">10.1016/j.comgeo.2012.02.010</a>'
  apa: 'Chen, C., &#38; Kerber, M. (2013). An output sensitive algorithm for persistent
    homology. <i>Computational Geometry: Theory and Applications</i>. Elsevier. <a
    href="https://doi.org/10.1016/j.comgeo.2012.02.010">https://doi.org/10.1016/j.comgeo.2012.02.010</a>'
  chicago: 'Chen, Chao, and Michael Kerber. “An Output Sensitive Algorithm for Persistent
    Homology.” <i>Computational Geometry: Theory and Applications</i>. Elsevier, 2013.
    <a href="https://doi.org/10.1016/j.comgeo.2012.02.010">https://doi.org/10.1016/j.comgeo.2012.02.010</a>.'
  ieee: 'C. Chen and M. Kerber, “An output sensitive algorithm for persistent homology,”
    <i>Computational Geometry: Theory and Applications</i>, vol. 46, no. 4. Elsevier,
    pp. 435–447, 2013.'
  ista: 'Chen C, Kerber M. 2013. An output sensitive algorithm for persistent homology.
    Computational Geometry: Theory and Applications. 46(4), 435–447.'
  mla: 'Chen, Chao, and Michael Kerber. “An Output Sensitive Algorithm for Persistent
    Homology.” <i>Computational Geometry: Theory and Applications</i>, vol. 46, no.
    4, Elsevier, 2013, pp. 435–47, doi:<a href="https://doi.org/10.1016/j.comgeo.2012.02.010">10.1016/j.comgeo.2012.02.010</a>.'
  short: 'C. Chen, M. Kerber, Computational Geometry: Theory and Applications 46 (2013)
    435–447.'
corr_author: '1'
date_created: 2018-12-11T12:00:27Z
date_published: 2013-05-01T00:00:00Z
date_updated: 2025-09-29T13:26:21Z
day: '01'
department:
- _id: HeEd
doi: 10.1016/j.comgeo.2012.02.010
external_id:
  isi:
  - '000314437000004'
intvolume: '        46'
isi: 1
issue: '4'
language:
- iso: eng
month: '05'
oa_version: None
page: 435 - 447
publication: 'Computational Geometry: Theory and Applications'
publication_status: published
publisher: Elsevier
publist_id: '3796'
quality_controlled: '1'
related_material:
  record:
  - id: '3367'
    relation: earlier_version
    status: public
scopus_import: '1'
status: public
title: An output sensitive algorithm for persistent homology
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 46
year: '2013'
...