Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

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.

I don't have the exact references around but it seems that this document contains all the details: http://www2.math.uni-paderborn.de/fileadmin/Mathematik/AG-Eisenbrand/publications/diss.pdf

share|improve this answer
    
See also the Wikipedia description of Gomory cuts: en.wikipedia.org/wiki/Cutting-plane_method#Gomory.27s_cut –  Joseph O'Rourke Sep 14 '12 at 11:39

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.