Optimal Reconstruction Might be Hard - AGPIG Accéder directement au contenu
Article Dans Une Revue Discrete and Computational Geometry Année : 2013

Optimal Reconstruction Might be Hard

Résumé

Given as input a point set S that samples a shape A, the condition required for inferring Betti numbers of A from S in polynomial time is much weaker than the conditions required by any known polynomial time algorithm for producing a topologically correct approximation of A from S. Under the former condition which we call the weak precondition, we investigate the question whether a polynomial time algorithm for reconstruction exists. As a first step, we provide an algorithm which outputs an approximation of the shape with the correct Betti numbers under a slightly stronger condition than the weak precondition. Unfortunately, even though our algorithm terminates, its time complexity is unbounded. We then identify at the heart of our algorithm a test which requires answering the following question: given two 2-dimensional simplicial complexes L contained in K, does there exist a simplicial complex containing L and contained in K which realizes the persistent homology of L into K? We call this problem the homological simplification of the pair (K,L) and prove that this problem is NP-complete, using a reduction from 3SAT.
Fichier principal
Vignette du fichier
2011-dcg-homological-simplification.pdf (494.47 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00785089 , version 1 (05-02-2013)

Identifiants

Citer

Dominique Attali, André Lieutier. Optimal Reconstruction Might be Hard. Discrete and Computational Geometry, 2013, 49 (2), pp.133-156. ⟨10.1007/s00454-012-9475-8⟩. ⟨hal-00785089⟩
325 Consultations
221 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More