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

This question was probably asked before but here goes. I have a convex polytope given by $Ax\leq b$ for a specific integer matrix $A$ and integer vector $b$. I need a simple method/result on how to check existence of a lattice point inside this polytope. I realize that this is not a very precise request but any kind of input would be nice. I'm not sure if it matters but $A$ is a sparse matrix.

share|improve this question
1  
What precisely do you mean by the expression $Ax \leq b$? –  Stefan Kohl Jul 21 '13 at 13:02
4  
This is integer programming (feasibility); NP-hard in general. See en.wikipedia.org/wiki/Integer_programming –  Abhinav Kumar Jul 21 '13 at 13:41
1  
I doubt this would help (because computing the volume is difficult), but you may be interested in Minkowski's lattice-point theorem, which infers the existence of a lattice point from the volume. –  Joseph O'Rourke Jul 21 '13 at 14:24
2  
Note that while the general problem is hard, it is often easy to solve specific instances, so if you tell us more about your problem, you might get more useful info. –  Igor Rivin Jul 21 '13 at 16:52
1  
Without the symmetry requirement, a convex polytope can have arbitrarily large volume and no lattice point. –  Gerry Myerson Jul 21 '13 at 23:44

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.