Abstract | ||
---|---|---|
We consider the problem of deciding whether the persistent homology group of a simplicial pair (K,L) can be realized as the homology of some complex H*(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-hard. |
Year | DOI | Venue |
---|---|---|
2013 | 10.1016/j.comgeo.2014.08.010 | Computational Geometry: Theory and Applications |
Keywords | Field | DocType |
complex h,simplicial pair,persistent homology group,scalar function,level set,homological reconstruction,medical image,tolerance constraint,sublevel set,homology,persistence,np hard problems | Discrete mathematics,Combinatorics,Visualization,Scalar (physics),Level set,Persistent homology,Mathematics | Conference |
Volume | Issue | ISSN |
48 | 8 | 0925-7721 |
Citations | PageRank | References |
1 | 0.34 | 17 |
Authors | ||
5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Dominique Attali | 1 | 413 | 35.68 |
Ulrich Bauer | 2 | 102 | 10.84 |
Olivier Devillers | 3 | 788 | 70.63 |
marc glisse | 4 | 267 | 24.05 |
André Lieutier | 5 | 358 | 28.27 |