Homological reconstruction and simplification in R3 Journal Article


Author(s): Attali, Dominique; Bauer, Ulrich; Devillers, Olivier; Glisse, Marc; Lieutier, André
Article Title: Homological reconstruction and simplification in R3
Alternate Title: Computational Geometry: Theory and Applications
Affiliation IST Austria
Abstract: We consider the problem of deciding whether the persistent homology group of a simplicial pair (K,L)(K,L) can be realized as the homology H⁎(X)H⁎(X) of some complex X with L⊂X⊂KL⊂X⊂K. We show that this problem is NP-complete even if K is embedded in R3R3. As a consequence, we show that it is NP-hard to simplify level and sublevel sets of scalar functions on S3S3 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.
Keywords: Homology; Persistence; NP-hard problems
Journal Title: Computational Geometry: Theory and Applications
Volume: 48
Issue 8
ISSN: 0925-7721
Publisher: Elsevier  
Date Published: 2015-09-01
Start Page: 606
End Page: 621
URL:
DOI: 10.1016/j.comgeo.2014.08.010
Notes: This work was initiated during the 10th McGill–INRIA Workshop on Computational Geometry at the Bellairs Research Institute. The authors wish to thank all the participants for creating a pleasant and stimulating atmosphere, in particular Nina Amenta for discussions leading to a first version of Theorem 1. Some of the authors were partially supported by the ANR project TopData ANR-13-BS01-0008, the European project CG-Learning (contract 255827), and the Toposys project FP7-ICT-318493-STREP.
Open access: yes (repository)
IST Austria Authors
  1. Ulrich Bauer
    12 Bauer
Related IST Austria Work