# The number of hyperplanes determining the integer points of a polyhedron

This question is inspired by this one.

Let $P \subset \mathbb R_{+}^n$ be a convex polyhedron whose complement in $\mathbb R_{+}^n$ has finite volume. Let $Int(P) = P \cap \mathbb N^n$. (For motivation: they are the set of exponent vectors of integrally closed, $0$-dimensional monomial ideals in $\mathbb C[x_1,\cdots, x_n]$, but we probably don't need it here).

Question 1: Is there a nice characterization (perhaps using the corner points) of when we can find one hyperplane $H$ that separate $Int(P)$ and its complement in $\mathbb N^n$? Namely, such that $Int(P)$ is precisely the intersection of a closed half-space defined by $H$ and $\mathbb N^n$?

Question 2: More generally, we can look at the least number of hyperplanes needed to cut out $Int(P)$. Is such number studied in the literature? Any good algorithm to find it?

Some examples: for $n=2$, let $P$ be the convex hull of $\{(0,2); (1,1); (3,0)\}$. Then one can find $H : 2x+3y=5$. But for the convex hull of $\{(0,3); (1,1); (3,0)\}$, it is easy to see that one needs $2$ lines.

-

The answer to both your questions is Gomory cuts. From a non-interger extreme point $x$ of $P$ it is easy to find an hyperplane $H$ which separate $x$ from $Int(P)$. Such an hyperplane is called a Gomory cut. It can be shown that by applying this procedure a finite number of time one can describe $Int(P)$ as a finite intersection of halfspaces.