Homological reconstruction and simplification in R3 Conference Paper

Author(s): Attali, Dominique; Bauer, Ulrich; Devillers, Olivier; Glisse, Marc; Lieutier, André
Title: Homological reconstruction and simplification in R3
Affiliation IST Austria
Abstract: 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.
Conference Title: SoCG: Symposium on Computational Geometry
Conference Dates: June 17-20, 2013
Conference Location: Rio de Janeiro, Brazil
ISBN: 978-1-4503-2594-3
Publisher: ACM  
Location: New York, NY, USA
Date Published: 2013-06-01
Start Page: 117
End Page: 125
Copyright Statement: Homology; NP-hard problems; Persistence
Sponsor: 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).
Open access: yes (repository)
IST Austria Authors
  1. Ulrich Bauer
    12 Bauer
Related IST Austria Work