The randomized integer convex hull (Q1764169): Difference between revisions

Let \({\mathbb Z}^d\) denote the \(d\)-dimensional integer lattice. Let \(K\subset {\mathbb R}^d\) be a convex body, i.e. a convex compact set with nonempty interior. The integer convex hull \(I(K)\) of \(K\) is the convex hull of all lattice points in \(K\), i.e. \(I(K) = conv(K\cap {\mathbb Z}^d)\). \(I(K)\) is a convex polytope which is of central interest in integer programming. For instance, when maximizing a linear function \(f\) on the integer points in \(K\), one looks for the maximum of \(f\) on \(I(K)\). The authors consider a randomized version of the integer convex hull and expected missed area. The lattice \({\mathbb Z}^d\) is replaced by \(L\), a randomly translated and rotated copy of \({\mathbb Z}^d\), i.e. \(I_L(K) = conv(K\cap L)\). More precisely, for a translation vector \(t\in [0,1)^d\) and a rotation \(\rho\in SO(d)\) around the origin, we set \(L_{t,\rho}= \rho\,({\mathbb Z}^d+t)\), and define \({\mathcal L}\)= \(\{L_{t, \rho}:t\in [0,1)^d, \rho \in SO(d)\}\). A probability measure on \({\mathcal L}\) is defined as the product of Haar measures on \([0,1)^d\) and \(SO(d)\) respectively. The article is organized as follows. In section 2 properties of the Macbeath regions are given. In section 3, the upper and lower bounds for the expected number of vertices in terms of the volume of the so-called Macbeath region are obtained. In section 4, in the planar case, the similar problem for expected missed area is investigated. The last section contains some open problems.