Point Containment in the Integer Hull of a Polyhedron
Ernst Althaus, Friedrich Eisenbrand, Stefan Funke, Kurt Mehlhorn
We show that the point containment problem in the integer hull of a
polyhedron, which is defined by $m$ inequalities, with
coefficients of at most $\varphi$ bits can be solved in
time $\bigO(m+\varphi)$ in the two-dimensional case and in expected time
$\bigO(m+\varphi^2 \log m)$ in any fixed dimension. This improves on the
algorithm which is based on the equivalence of separation and
optimization and on a direct algorithm (SODA 97) for the
two-dimensional case.
PDF