Homological Reconstruction and Simplification in R3

Dominique Attali 1 Ulrich Bauer 2 Olivier Devillers 3 Marc Glisse 3 André Lieutier 4
1 GIPSA-AGPIG - AGPIG
GIPSA-DIS - Département Images et Signal
3 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
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-hard.
Type de document :
Communication dans un congrès
29th Symposium on Computational Geometry (SoCG), Jun 2013, Rio de Janeiro, Brazil. ACM, pp.117-125, 2013, 〈10.1145/2462356.2462373〉
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger


https://hal.inria.fr/hal-00833791
Contributeur : Olivier Devillers <>
Soumis le : jeudi 13 juin 2013 - 15:08:22
Dernière modification le : jeudi 11 janvier 2018 - 16:22:01
Document(s) archivé(s) le : mardi 4 avril 2017 - 21:42:16

Fichiers

hal-version.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Dominique Attali, Ulrich Bauer, Olivier Devillers, Marc Glisse, André Lieutier. Homological Reconstruction and Simplification in R3. 29th Symposium on Computational Geometry (SoCG), Jun 2013, Rio de Janeiro, Brazil. ACM, pp.117-125, 2013, 〈10.1145/2462356.2462373〉. 〈hal-00833791〉

Partager

Métriques

Consultations de la notice

435

Téléchargements de fichiers

219