Integer lattice points in a closed convex polyhedron and close to the polyhedron's extreme points

34 Views Asked by At

In the 2-D Euclidean space, the angle formed by the intersection of two closed half-spaces, $H_{1}, H_{2}$, with outer normals $\hat{n}_{1}, \hat{n}_{2}$ can be measured as obtuse or acute. It is acute if the angle between the normals is $< \pi/2$ degrees) and obtuse if that angle is $> \pi/2$. In 2-D, it can be proved that if this angle is obtuse, then the polyhedron $H_{1} \cap H_{2}$ contains an integer lattice point within $l^{1}$-distance $1$ of $\partial H_{1} \cap \partial H_{2}$. The value of this (easy) result is that if the two half-spaces are the constraints in an Integer Linear Program (ILP), then its relaxation to an LP with solution (on) $\partial H_{1} \cap \partial H_{2}$ is close the solution of the ILP.

I am looking to learn how far this has been generalized to LP's of higher dimensions and more constraints, with all inequality constraints sharp: $H_{k}, k = 1, 2, \ldots, K$ are still closed half-spaces. The point $\partial H_{1} \cap \partial H_{2}$ from the 2-D case generalizes to an extreme point $v$ of the polyhedron $$ P = \cap_{k=1}^{K} H_{k}, $$ and we want to "measure the obtuseness" of the polyhedral angle with vertex $v$. If there is such a measure, the next question is, can we generalize the above statement in bold-face: something like "if the polyhedral angle at $v$ is obtuse, then an integer lattice point in $P$ closest to $v$ is within $l^{1}$-distance $1$ from $v$."?