HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Reports

Homological reconstruction and simplification in R3

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 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-complete.
Document type :
Reports
Complete list of metadata

Cited literature [19 references]  Display  Hide  Download

https://hal.inria.fr/hal-00761208
Contributor : Olivier Devillers Connect in order to contact the contributor
Submitted on : Wednesday, December 5, 2012 - 10:09:35 AM
Last modification on : Friday, January 21, 2022 - 3:10:56 AM
Long-term archiving on: : Saturday, December 17, 2016 - 8:28:07 PM

File

RR-8169.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00761208, version 1

Collections

Citation

Dominique Attali, Ulrich Bauer, Olivier Devillers, Marc Glisse, André Lieutier. Homological reconstruction and simplification in R3. [Research Report] RR-8169, INRIA. 2012. ⟨hal-00761208⟩

Share

Metrics

Record views

519

Files downloads

188