@misc{1711.08436,
author = {Xavier Goaoc and Pavel Paták and Zuzana Patáková and Martin Tancer and Uli Wagner},
title = {{S}hellability is {NP}-complete},
year = {2017},
eprint = {1711.08436},
note = {arXiv:1711.08436v1}
}

We prove that for every $d\geq 2$, deciding if a pure, $d$-dimensional, simplicial complex is shellable is NP-hard, hence NP-complete. This resolves a question raised, e.g., by Danaraj and Klee in 1978. Our reduction also yields that for every $d \ge 2$ and $k \ge 0$, deciding if a pure, $d$-dimensional, simplicial complex is $k$-decomposable is NP-hard. For $d \ge 3$, both problems remain NP-hard when restricted to contractible pure $d$-dimensional complexes.

@misc{1711.08137,
author = {Zheng Liu and Rongjie Lai and Huayan Zhang and Chunlin Wu},
title = {{T}riangulated {S}urface {D}enoising using {H}igh {O}rder {R}egularization with {D}ynamic {W}eights},
year = {2017},
eprint = {1711.08137},
note = {arXiv:1711.08137v1}
}

Recovering high quality surfaces from noisy triangulated surfaces is a fundamental important problem in geometry processing. Sharp features including edges and corners can not be well preserved in most existing denoising methods except the recent total variation (TV) and $\ell_0$ regularization methods. However, these two methods have suffered producing staircase artifacts in smooth regions. In this paper, we first introduce a second order regularization method for restoring a surface normal vector field, and then propose a new vertex updating scheme to recover the desired surface according to the restored surface normal field. The proposed model can preserve sharp features and simultaneously suppress the staircase effects in smooth regions which overcomes the drawback of the first order models. In addition, the new vertex updating scheme can prevent ambiguities introduced in existing vertex updating methods. Numerically, the proposed high order model is solved by the augmented Lagrangian method with a dynamic weighting strategy. Intensive numerical experiments on a variety of surfaces demonstrate the superiority of our method by visually and quantitatively.