Discrete volume polyhedrization: Complexity and bounds on performance

Given a set M ⊂ Z³, an enclosing polyhedron for M is any polyhedron P such that the set of integer points contained in P is precisely M. Representing a discrete volume by an enclosing polyhedron is a fundamental problem in visualization. In this paper we propose the first proof of the long-standing conjecture that the problem of finding an enclosing polyhedron with a minimal number of 2-facets is strongly NP-hard. We also provide a lower bound for that number.