About the Decidability of Polyhedral Separability in the Lattice $$mathbb {Z}^d$$

The recognition of primitives in digital geometry is deeply linked with separability problems. This framework leads us to consider the following problem of pattern recognition : given a finite lattice set (Ssubset mathbb {Z}^d) and a positive integer n, is it possible to separate S from (mathbb {Z}^d setminus S) by n half-spaces? In other words, does there exist a polyhedron P defined by at most n half-spaces satisfying (Pcap mathbb {Z}^d = S)? The difficulty comes from the infinite number of constraints generated by all the points of (mathbb {Z}^dsetminus S). It makes the decidability of the problem non-straightforward since the classical algorithms of polyhedral separability can not be applied in this framework. We conjecture that the problem is nevertheless decidable and prove it under some assumptions: in arbitrary dimension, if the interior of the convex hull of S contains at least one lattice point or if the dimension d is 2 or if the dimension (d=3) and S is not in a specific configuration of lattice width 0 or 1. The proof strategy is to reduce the set of outliers (mathbb {Z}^dsetminus S) to its minimal elements according to a partial order “is in the shadow of.” These minimal elements are called the lattice jewels of S. We prove that under some assumptions, the set S admits only a finite number of lattice jewels. The result about the decidability of the problem is a corollary of this fundamental property.