The randomized integer convex hull
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.
- On random convex hulls
- On the convex hull of random points in a polytope
- Convex Hulls of Random Order Types
- On a random convex hull in an n-ball
- Random approximation of convex bodies
- Random convex hulls: a variance revisited
- An explicit formula about the convex hull of random points
- EXPECTED MEAN WIDTH OF THE RANDOMIZED INTEGER CONVEX HULL
- Computing the integer hull of convex polyhedral sets
- Random monomial ideals
- Average complexity of a gift-wrapping algorithm for determining the convex hull of randomly given points
- Approximation of convex sets by polytopes
- Random points and lattice points in convex bodies
- scientific article; zbMATH DE number 2209715 (Why is no real title available?)
- EXPECTED MEAN WIDTH OF THE RANDOMIZED INTEGER CONVEX HULL
This page was built for publication: The randomized integer convex hull
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1764169)
