Skip to main content
1 of 3
Hailong Dao
  • 30.5k
  • 5
  • 102
  • 188

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.

Hailong Dao
  • 30.5k
  • 5
  • 102
  • 188