Earlier Version
Homological reconstruction and simplification in R3
Attali D, Bauer U, Devillers O, Glisse M, Lieutier A. 2013. Homological reconstruction and simplification in R3. Proceedings of the 29th annual symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, 117–125.
Download (ext.)
Conference Paper
| Published
| English
Scopus indexed
Author
Attali, Dominique;
Bauer, UlrichISTA 
;
Devillers, Olivier;
Glisse, Marc;
Lieutier, André
;
Devillers, Olivier;
Glisse, Marc;
Lieutier, AndréDepartment
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 ℝ3. 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.
Publishing Year
Date Published
2013-06-01
Proceedings Title
Proceedings of the 29th annual symposium on Computational Geometry
Acknowledgement
Some of the authors were partially supported by the GIGA ANR grant (contract ANR-09-BLAN-0331-01) and the European project CG-Learning (contract 255827).
Page
117 - 125
Conference
SoCG: Symposium on Computational Geometry
Conference Location
Rio de Janeiro, Brazil
Conference Date
2013-06-17 – 2013-06-20
IST-REx-ID
Cite this
Attali D, Bauer U, Devillers O, Glisse M, Lieutier A. Homological reconstruction and simplification in R3. In: Proceedings of the 29th Annual Symposium on Computational Geometry. ACM; 2013:117-125. doi:10.1145/2462356.2462373
Attali, D., Bauer, U., Devillers, O., Glisse, M., & Lieutier, A. (2013). Homological reconstruction and simplification in R3. In Proceedings of the 29th annual symposium on Computational Geometry (pp. 117–125). Rio de Janeiro, Brazil: ACM. https://doi.org/10.1145/2462356.2462373
Attali, Dominique, Ulrich Bauer, Olivier Devillers, Marc Glisse, and André Lieutier. “Homological Reconstruction and Simplification in R3.” In Proceedings of the 29th Annual Symposium on Computational Geometry, 117–25. ACM, 2013. https://doi.org/10.1145/2462356.2462373.
D. Attali, U. Bauer, O. Devillers, M. Glisse, and A. Lieutier, “Homological reconstruction and simplification in R3,” in Proceedings of the 29th annual symposium on Computational Geometry, Rio de Janeiro, Brazil, 2013, pp. 117–125.
Attali D, Bauer U, Devillers O, Glisse M, Lieutier A. 2013. Homological reconstruction and simplification in R3. Proceedings of the 29th annual symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, 117–125.
Attali, Dominique, et al. “Homological Reconstruction and Simplification in R3.” Proceedings of the 29th Annual Symposium on Computational Geometry, ACM, 2013, pp. 117–25, doi:10.1145/2462356.2462373.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
Open Access
Google Scholar