Recognition of digital polyhedra with a fixed number of faces

Abstract : The main task of the paper is to investigate the question of the recognition of digital polyhedra with a fixed number of facets: given a finite lattice set S ⊂ Zd and an integer n, does there exist a polyhedron P of R^d with n facets and P ∩ Z^d = S? The problem can be stated in terms of polyhedral separation of the set S and its complementary Z^d /S. The difficulty is that the set Z^d /S is not finite. It makes the classical algorithms intractable for this purpose. This problem is overcome by introducing a partial order "is in the shadow of ". Its minimal lattice elements are called the jewels. The main result of the paper is within the domain of the geometry of numbers: under some assumptions on the lattice set S (if S ⊂ Z² is not degenerated or if the interior of the convex hull of S ⊂ Z^d contains an integer point), it has only a finite number of lattice jewels. In this case, we provide an algorithm of recognition of a digital polyhedron with n facets which always finishes.
Complete list of metadatas

Cited literature [14 references]  Display  Hide  Download
Contributor : Yan Gerard <>
Submitted on : Monday, February 18, 2019 - 4:57:12 PM
Last modification on : Monday, January 20, 2020 - 12:14:06 PM
Long-term archiving on: Sunday, May 19, 2019 - 7:25:32 PM


Files produced by the author(s)


Public Domain




Yan Gérard. Recognition of digital polyhedra with a fixed number of faces. DGCI ( Discrete Geometry for Computer Imagery ) 2016, Apr 2016, Nantes, France. ⟨10.1007/978-3-319-32360-2_32⟩. ⟨hal-02023827⟩



Record views


Files downloads