Covering Minima and Lattice Point Free Convex Bodies
Covering Minima and Lattice Point Free Convex Bodies
复制标题
覆盖极小值和无格点凸体
DOI：
10.1007/3-540-17179-7_12
复制
发表时间：
1986
影响因子：
6.4
通讯作者：
L. Lovász
中科院分区：
文献类型：
--
作者：
R. Kannan;L. Lovász
假设K是欧氏n-空间Rn中的非零体积的凸集，并且它关于原点对称（即，如果x属于K，则-x也属于K）。对于任意真实的数t，设tK ={tx：x ∈ K}。所有正的真实的数t上的下确界，如果tK的一个副本被放置在每个整数点的中心，所有的Rn被覆盖，被称为K的"覆盖半径"（相对于晶格Zn）。覆盖半径及其相关量在数的几何中得到了广泛的研究。在本文中，我们定义和研究的“覆盖最小值”的凸体不一定是对称的原点，覆盖半径将是一个特殊的情况下，这些最小值之一。这种扩展一般凸体除其他事项外，应用程序的算法，这是我们最初的动机。这一动机将在后面详细解释。利用本文的结果导出了格点自由凸体的宽度的界，并分析了它们的结构。
Suppose K is a convex set of nonzero volume in Euclidean n-space Rn and it is symmetric about the origin (i.e., if x belongs to K, so does - x). For any real number t, let tK={tx : x∈K}. The infimum over all positive real numbers t such that if a copy of tK is placed centered at every integer point, all of Rn is covered, is called the “covering radius” of K (with respect to the lattice Zn). The covering radius and related quantities have been studied extensively in Geometry of Numbers. In this paper, we define and study the “covering minima” of a convex body which is not necessarily symmetric about the origin; the covering radius will be a special case of one of of these minima. This extension to general convex bodies has among other things, applications to algorithms for Integer Programming which was our initial motivation. This motivation is explained in some detail later. We use the results of the paper to derive bounds on the width of lattice point free convex bodies and analyze their structure.