Homological Reconstruction and Simplification in R3Report as inadecuate




Homological Reconstruction and Simplification in R3 - Download this document for free, or read online. Document in PDF available to download.

1 GIPSA-AGPIG - AGPIG GIPSA-DIS - Département Images et Signal 2 IST Austria - Institute of Science and Technology Austria 3 GEOMETRICA - Geometric computing CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France 4 MGMI - Modélisation Géométrique & Multirésolution pour l-Image LJK - Laboratoire Jean Kuntzmann

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 contained in X and X contained in 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.

Keywords : homology NP-hard problems persistence





Author: Dominique Attali - Ulrich Bauer - Olivier Devillers - Marc Glisse - André Lieutier -

Source: https://hal.archives-ouvertes.fr/



DOWNLOAD PDF




Related documents