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
Résumé : 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.
Type de document :
Rapport
[Research Report] RR-8169, INRIA. 2012


https://hal.inria.fr/hal-00761208
Contributeur : Olivier Devillers <>
Soumis le : mercredi 5 décembre 2012 - 10:09:35
Dernière modification le : samedi 17 septembre 2016 - 01:36:52

Fichier

RR-8169.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00761208, version 1

Collections

Citation

Dominique Attali, Ulrich Bauer, Olivier Devillers, Marc Glisse, André Lieutier. Homological reconstruction and simplification in R3. [Research Report] RR-8169, INRIA. 2012. <hal-00761208>

Exporter

Partager

Métriques

Consultations de
la notice

740

Téléchargements du document

125