conference paper published yes Dominique Attali author Ulrich Bauer author 2ADD483A-F248-11E8-B48F-1D18A9856A870000-0002-9683-0724 Olivier Devillers author Marc Glisse author André Lieutier author HeEd department SoCG: Symposium on Computational Geometry 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. ACM2013Rio de Janeiro, Brazil eng 10.1145/2462356.2462373 117 - 125 https://research-explorer.ista.ac.at/record/1805 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.” <i>Proceedings of the 29th Annual Symposium on Computational Geometry</i>, ACM, 2013, pp. 117–25, doi:<a href="https://doi.org/10.1145/2462356.2462373">10.1145/2462356.2462373</a>. D. Attali, U. Bauer, O. Devillers, M. Glisse, and A. Lieutier, “Homological reconstruction and simplification in R3,” in <i>Proceedings of the 29th annual symposium on Computational Geometry</i>, Rio de Janeiro, Brazil, 2013, pp. 117–125. Attali D, Bauer U, Devillers O, Glisse M, Lieutier A. Homological reconstruction and simplification in R3. In: <i>Proceedings of the 29th Annual Symposium on Computational Geometry</i>. ACM; 2013:117-125. doi:<a href="https://doi.org/10.1145/2462356.2462373">10.1145/2462356.2462373</a> Attali, D., Bauer, U., Devillers, O., Glisse, M., &#38; Lieutier, A. (2013). Homological reconstruction and simplification in R3. In <i>Proceedings of the 29th annual symposium on Computational Geometry</i> (pp. 117–125). Rio de Janeiro, Brazil: ACM. <a href="https://doi.org/10.1145/2462356.2462373">https://doi.org/10.1145/2462356.2462373</a> D. Attali, U. Bauer, O. Devillers, M. Glisse, A. Lieutier, in:, Proceedings of the 29th Annual Symposium on Computational Geometry, ACM, 2013, pp. 117–125. Attali, Dominique, Ulrich Bauer, Olivier Devillers, Marc Glisse, and André Lieutier. “Homological Reconstruction and Simplification in R3.” In <i>Proceedings of the 29th Annual Symposium on Computational Geometry</i>, 117–25. ACM, 2013. <a href="https://doi.org/10.1145/2462356.2462373">https://doi.org/10.1145/2462356.2462373</a>. 28122018-12-11T11:59:44Z2026-06-18T17:57:27Z