2
$\begingroup$

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.

$\endgroup$
10
  • 1
    $\begingroup$ What precisely do you mean by the expression $Ax \leq b$? $\endgroup$
    – Stefan Kohl
    Jul 21, 2013 at 13:02
  • 4
    $\begingroup$ This is integer programming (feasibility); NP-hard in general. See en.wikipedia.org/wiki/Integer_programming $\endgroup$ Jul 21, 2013 at 13:41
  • 1
    $\begingroup$ 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. $\endgroup$ Jul 21, 2013 at 14:24
  • 2
    $\begingroup$ 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. $\endgroup$
    – Igor Rivin
    Jul 21, 2013 at 16:52
  • 1
    $\begingroup$ Without the symmetry requirement, a convex polytope can have arbitrarily large volume and no lattice point. $\endgroup$ Jul 21, 2013 at 23:44

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.