Recognition of digital polyhedra with a fixed number of faces is decidable in dimension 3

Abstract : 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^d \ S 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. 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 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.
Complete list of metadatas

Cited literature [12 references]  Display  Hide  Download
Contributor : Yan Gerard <>
Submitted on : Monday, February 18, 2019 - 5:33:30 PM
Last modification on : Monday, January 20, 2020 - 12:14:06 PM
Long-term archiving on: Sunday, May 19, 2019 - 6:52:30 PM


Files produced by the author(s)


Public Domain




Yan Gerard. Recognition of digital polyhedra with a fixed number of faces is decidable in dimension 3. 20th IAPR International Conference on Discrete Geometry for Computer Imagery (DGCI 2017), Sep 2017, Vienne, Austria. pp.279-290, ⟨10.1007%2F978-3-319-66272-5_23⟩. ⟨hal-02023886⟩



Record views


Files downloads