Homological reconstruction and simplification in R3
Homological reconstruction and simplification in R3
复制标题
R3 中的同源重建和简化
DOI：
10.1145/2462356.2462373
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
A. Lieutier
中科院分区：
文献类型：
--
作者：
D. Attali;Ulrich Bauer;O. Devillers;M. Glisse;A. Lieutier
本文考虑判定单纯对（K，L）的持久同调群能否实现为复形H*（X）的同调群，其中L <$X <$K.我们表明，这个问题是NP完全的，即使K是嵌入在R3。因此，我们表明，它是NP-难的简化水平和子水平集的标量函数在S3在给定的公差约束。这个问题与医学图像的等值面可视化有关。我们还展示了标量函数的井群理论的一个含义：不是每个井群都能被某个水平集实现，判断一个井群是否能被实现是NP困难的。
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.