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.
Domaines
Géométrie algorithmique [cs.CG]
Origine : Fichiers produits par l'(les) auteur(s)
Loading...