8739 articles  [version française]

hal-00761208, version 1

Homological reconstruction and simplification in R3

Dominique Attali () 1, Ulrich Bauer (http://pub.ist.ac.at/~bauer/) 2, Olivier Devillers (, http://www-sop.inria.fr/members/Olivier.Devillers/) 3, Marc Glisse () a3, André Lieutier 4

N° RR-8169 (2012)

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 R3. 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-complete.

  • a –  INRIA
  • 1:  Grenoble Images Parole Signal Automatique (GIPSA-lab)
  • CNRS : UMR5216 – Université Joseph Fourier - Grenoble I – Université Pierre-Mendès-France - Grenoble II – Université Stendhal - Grenoble III – Institut Polytechnique de Grenoble - Grenoble Institute of Technology
  • 2:  Institute of Science and Technology [Austria] (IST Austria)
  • IST Austria
  • 3:  GEOMETRICA (INRIA Sophia Antipolis / INRIA Saclay - Ile de France)
  • 4:  Dassault Systèmes
  • Dassault Systèmes
  • Domain : Computer Science/Computational Geometry
  • Internal note : RR-8169
  • hal-00761208, version 1
  • oai:hal.inria.fr:hal-00761208
  • From: 
  • Submitted on: Wednesday, 5 December 2012 10:09:35
  • Updated on: Wednesday, 5 December 2012 11:24:14