Computing Two-Dimensional Integer Hulls
Computing Two-Dimensional Integer Hulls
复制标题
计算二维整数外壳
DOI：
10.1137/s009753979528977x
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
Warwick Harvey
中科院分区：
文献类型：
--
作者：
Warwick Harvey
给出了一种计算定义可能无界二维凸多边形R的整数壳的最小线性不等式集的最优算法。该算法的输入是定义R的线性不等式集，所计算的整数壳是R的整数点的凸壳。证明了整数壳最多有O（n log Amax）个不等式，其中n为输入不等式的个数，Amax为最大输入系数的大小。通过证明整数船体在最坏情况下可能存在$\Omega(n \log A_{max})$不等式，证明了所提出的算法的复杂度为O(n log Amax)，并且该算法是最优的。
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 Amax) inequalities, where n is the number of input inequalities and Amax is the magnitude of the largest input coefficient. It is shown that the algorithm presented has complexity O(n log Amax) and that this is optimal by proving that the integer hull may have $\Omega(n \log A_{max})$ inequalities in the worst case.