Computing Two-Dimensional Integer Hulls
Warwick Harvey · SIAM Journal on Computing · 1999
An optimal algorithm is presented for computing the smallest set of linear inequalities that define the integer hull of a possibly unbounded two-dimensional convex polygon R. Input to the algorithm is a set of linear inequalities defining R, and the integer hull computed is the convex hull of the integer points of R. It is proven that the integer hull has at most O(n log A max ) inequalities, where n is the number of input inequalities and A max is the magnitude of the largest input coefficient. It is shown that the algorithm presented has complexity O(n log A max ) and that this is optimal by proving that the integer hull may have $\Omega(n \log A_{max})$ inequalities in the worst case.