Homological reconstruction and simplification in R3 - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2012

Homological reconstruction and simplification in R3

Résumé

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.
Nous considérons le problème de décider si le groupe d'homologie persistant de la paire simpliciale (K, L) peut être réalisée comme l'homologie H∗(X) d'un complexe X vérifiant L ⊂ X ⊂ K. Nous montrons que ce problème est NP-complet, même si K est plongé dans R3. Nous en déduisons qu'il est NP-dur de simplifier les niveaux de fonctions scalaires sur S3 avec une tolérance fixée. Ce problème est pertinent pour la visualisation des isosurfaces dans les images médicales. Nous montrons également une conséquence pour la théorie des "well groups" de fonctions scalaires: il n' est pas toujours possible de réaliser un well group comme un ensemble de niveau, et décider si une telle réalisation est possible est NP-dur.
Fichier principal
Vignette du fichier
RR-8169.pdf (985.7 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00761208 , version 1 (05-12-2012)

Identifiants

  • HAL Id : hal-00761208 , version 1

Citer

Dominique Attali, Ulrich Bauer, Olivier Devillers, Marc Glisse, André Lieutier. Homological reconstruction and simplification in R3. [Research Report] RR-8169, INRIA. 2012. ⟨hal-00761208⟩
547 Consultations
214 Téléchargements

Partager

Gmail Facebook X LinkedIn More