---
_id: '2812'
abstract:
- lang: eng
  text: 'We consider the problem of deciding whether the persistent homology group
    of a simplicial pair (K, L) can be realized as the homology H* (X) of some complex
    X with L ⊂ X ⊂ K. We show that this problem is NP-complete even if K is embedded
    in ℝ3. As a consequence, we show that it is NP-hard to simplify level and sublevel
    sets of scalar functions on S3 within a given tolerance constraint. This problem
    has relevance to the visualization of medical images by isosurfaces. We also show
    an implication to the theory of well groups of scalar functions: not every well
    group can be realized by some level set, and deciding whether a well group can
    be realized is NP-hard.'
acknowledgement: Some of the authors were partially supported by the GIGA ANR grant
  (contract ANR-09-BLAN-0331-01) and the European project CG-Learning (contract 255827).
author:
- first_name: Dominique
  full_name: Attali, Dominique
  last_name: Attali
- first_name: Ulrich
  full_name: Bauer, Ulrich
  id: 2ADD483A-F248-11E8-B48F-1D18A9856A87
  last_name: Bauer
  orcid: 0000-0002-9683-0724
- first_name: Olivier
  full_name: Devillers, Olivier
  last_name: Devillers
- first_name: Marc
  full_name: Glisse, Marc
  last_name: Glisse
- first_name: André
  full_name: Lieutier, André
  last_name: Lieutier
citation:
  ama: 'Attali D, Bauer U, Devillers O, Glisse M, Lieutier A. Homological reconstruction
    and simplification in R3. In: <i>Proceedings of the 29th Annual Symposium on Computational
    Geometry</i>. ACM; 2013:117-125. doi:<a href="https://doi.org/10.1145/2462356.2462373">10.1145/2462356.2462373</a>'
  apa: 'Attali, D., Bauer, U., Devillers, O., Glisse, M., &#38; Lieutier, A. (2013).
    Homological reconstruction and simplification in R3. In <i>Proceedings of the
    29th annual symposium on Computational Geometry</i> (pp. 117–125). Rio de Janeiro,
    Brazil: ACM. <a href="https://doi.org/10.1145/2462356.2462373">https://doi.org/10.1145/2462356.2462373</a>'
  chicago: Attali, Dominique, Ulrich Bauer, Olivier Devillers, Marc Glisse, and André
    Lieutier. “Homological Reconstruction and Simplification in R3.” In <i>Proceedings
    of the 29th Annual Symposium on Computational Geometry</i>, 117–25. ACM, 2013.
    <a href="https://doi.org/10.1145/2462356.2462373">https://doi.org/10.1145/2462356.2462373</a>.
  ieee: D. Attali, U. Bauer, O. Devillers, M. Glisse, and A. Lieutier, “Homological
    reconstruction and simplification in R3,” in <i>Proceedings of the 29th annual
    symposium on Computational Geometry</i>, Rio de Janeiro, Brazil, 2013, pp. 117–125.
  ista: 'Attali D, Bauer U, Devillers O, Glisse M, Lieutier A. 2013. Homological reconstruction
    and simplification in R3. Proceedings of the 29th annual symposium on Computational
    Geometry. SoCG: Symposium on Computational Geometry, 117–125.'
  mla: Attali, Dominique, et al. “Homological Reconstruction and Simplification in
    R3.” <i>Proceedings of the 29th Annual Symposium on Computational Geometry</i>,
    ACM, 2013, pp. 117–25, doi:<a href="https://doi.org/10.1145/2462356.2462373">10.1145/2462356.2462373</a>.
  short: D. Attali, U. Bauer, O. Devillers, M. Glisse, A. Lieutier, in:, Proceedings
    of the 29th Annual Symposium on Computational Geometry, ACM, 2013, pp. 117–125.
conference:
  end_date: 2013-06-20
  location: Rio de Janeiro, Brazil
  name: 'SoCG: Symposium on Computational Geometry'
  start_date: 2013-06-17
date_created: 2018-12-11T11:59:44Z
date_published: 2013-06-01T00:00:00Z
date_updated: 2026-06-18T17:57:27Z
day: '01'
department:
- _id: HeEd
doi: 10.1145/2462356.2462373
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: http://hal.archives-ouvertes.fr/hal-00833791/
month: '06'
oa: 1
oa_version: Submitted Version
page: 117 - 125
publication: Proceedings of the 29th annual symposium on Computational Geometry
publication_status: published
publisher: ACM
publist_id: '4072'
quality_controlled: '1'
related_material:
  record:
  - id: '1805'
    relation: later_version
    status: public
scopus_import: 1
status: public
title: Homological reconstruction and simplification in R3
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2013'
...