Recognition of Digital Polyhedra with a Fixed Number of Faces Is Decidable in Dimension 3

摘要

We consider a conjecture on lattice polytopes Q ⊂ R~d (the vertices are integer points) or equivalently on finite subsets S ⊂ Z~d, Q and S being related by Q ∩ Z~d = S or Q = conv(S): given the vertices of Q or the list of points of S and an integer n, the problem to determine whether there exists a (rational) polyhedron P ⊂ R~d with at most n faces and verifying P ∩ Z~d = S is decidable. In terms of computational geometry, it's a problem of polyhedral separability of S and Z~dS but the infinite number of points of Z~d S makes it intractable for classical algorithms. This problem of digital geometry is however very natural since it is a kind of converse of Integer Linear Programming. The conjecture is proved in dimension d = 2 and in arbitrary dimension for non hollow lattice polytopes Q [6]. The purpose of the paper is to extend the result to hollow polytopes in dimension d = 3. An important part of the work is already done in [5] but it remains three special cases for which the set of outliers can not be reduced to a finite set: planar sets, pyramids and marquees. Each case is solved with a particular method which proves the conjecture in dimension d = 3.