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

Suppose we have a convex hull computed as the solution to a linear programming problem (via whatever method you want). Given this convex hull (and the inequalities that formed the convex hull) is there a fast way to compute the integer points on the surface of the convex hull? Or is the problem NP?

There exist ways to bound the number of integer points and to find the number of integer points inside convex hull, but I specifically want the points on the hull itself.

EDIT: Suppose the set of inequalities (the linear program) have integer coefficients /EDIT

share|improve this question
    
I guess that the surface of your convex hull is defined over $\mathbb Q$. The problem looks too broad and already hard in 2 dimensions (where, BTW, I don't see any particular benefit from having a convex hull). –  Wadim Zudilin Jun 24 '10 at 6:45
    
Right, ad I'm working in something more like 22 dimensions. It's definitely POSSIBLE to calculate, I already have an algorithm, I was just wondering if there's any fast way to do it. –  Michael Hoffman Jun 24 '10 at 13:08

1 Answer 1

up vote 3 down vote accepted

Because the facets of your convex hull are themselves polytopes (of one lower dimension—$d{=}21$ in your case), it seems your question is equivalent to asking how to count lattice points in a polytope. One paper on this topic is "The Many Aspects of Counting Lattice Points in Polytopes" by J. A. DeLoera. Section 4 is entitled, "Actually Counting: Modern Algorithms and Software." A key reference in that section is to a paper by Barvinok entitled, "Polynomial time algorithm for counting integral points in polyhedra when the dimension is fixed" (Math of Operations Research, Vol. 19, 769–779, 1994), whose title (polynomial time) seems to provide an answer of sorts to your question.

share|improve this answer

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.