---
OA_place: publisher
OA_type: free access
_id: '1805'
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 double-struck R3. As a consequence, we show that it is NP-hard to simplify
    level and sublevel sets of scalar functions on double-struck 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.'
article_processing_charge: No
article_type: original
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. <i>Computational Geometry: Theory and Applications</i>.
    2015;48(8):606-621. doi:<a href="https://doi.org/10.1016/j.comgeo.2014.08.010">10.1016/j.comgeo.2014.08.010</a>'
  apa: 'Attali, D., Bauer, U., Devillers, O., Glisse, M., &#38; Lieutier, A. (2015).
    Homological reconstruction and simplification in R3. <i>Computational Geometry:
    Theory and Applications</i>. Elsevier. <a href="https://doi.org/10.1016/j.comgeo.2014.08.010">https://doi.org/10.1016/j.comgeo.2014.08.010</a>'
  chicago: 'Attali, Dominique, Ulrich Bauer, Olivier Devillers, Marc Glisse, and André
    Lieutier. “Homological Reconstruction and Simplification in R3.” <i>Computational
    Geometry: Theory and Applications</i>. Elsevier, 2015. <a href="https://doi.org/10.1016/j.comgeo.2014.08.010">https://doi.org/10.1016/j.comgeo.2014.08.010</a>.'
  ieee: 'D. Attali, U. Bauer, O. Devillers, M. Glisse, and A. Lieutier, “Homological
    reconstruction and simplification in R3,” <i>Computational Geometry: Theory and
    Applications</i>, vol. 48, no. 8. Elsevier, pp. 606–621, 2015.'
  ista: 'Attali D, Bauer U, Devillers O, Glisse M, Lieutier A. 2015. Homological reconstruction
    and simplification in R3. Computational Geometry: Theory and Applications. 48(8),
    606–621.'
  mla: 'Attali, Dominique, et al. “Homological Reconstruction and Simplification in
    R3.” <i>Computational Geometry: Theory and Applications</i>, vol. 48, no. 8, Elsevier,
    2015, pp. 606–21, doi:<a href="https://doi.org/10.1016/j.comgeo.2014.08.010">10.1016/j.comgeo.2014.08.010</a>.'
  short: 'D. Attali, U. Bauer, O. Devillers, M. Glisse, A. Lieutier, Computational
    Geometry: Theory and Applications 48 (2015) 606–621.'
corr_author: '1'
date_created: 2018-12-11T11:54:06Z
date_published: 2015-06-03T00:00:00Z
date_updated: 2025-09-23T09:18:30Z
day: '03'
department:
- _id: HeEd
doi: 10.1016/j.comgeo.2014.08.010
ec_funded: 1
external_id:
  isi:
  - '000357353200006'
intvolume: '        48'
isi: 1
issue: '8'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.1016/j.comgeo.2014.08.010
month: '06'
oa: 1
oa_version: Published Version
page: 606 - 621
project:
- _id: 255D761E-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '318493'
  name: Topological Complex Systems
publication: 'Computational Geometry: Theory and Applications'
publication_status: published
publisher: Elsevier
publist_id: '5305'
quality_controlled: '1'
related_material:
  record:
  - id: '2812'
    relation: earlier_version
    status: public
scopus_import: '1'
status: public
title: Homological reconstruction and simplification in R3
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 48
year: '2015'
...