The randomized integer convex hull
type: Item
instance of: scholarly article
title: The randomized integer convex hull
zbMATH Open document ID: 1078.52005
author: Imre Bárány
author: Jiří Matoušek
published in: Discrete \& Computational Geometry
publication date: 2005-02-23T00:00:00Z
review text: 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.
reviewed by: Viktor Ohanyan
Mathematics Subject Classification ID: 52A22
Mathematics Subject Classification ID: 60D05
Mathematics Subject Classification ID: 60G57
zbMATH DE Number: 2138090
zbMATH Keywords: convex bodies
zbMATH Keywords: random polytopes
zbMATH Keywords: Macbeath region
zbMATH Keywords: expected number of vertices
zbMATH Keywords: expected missed area
MaRDI profile type: Publication
full work available at URL: s00454-003-0836-1
OpenAlex ID: W2035980752
Wikidata QID: Q101488227
DOI: 10.1007/S00454-003-0836-1
Recommended article: On random convex hulls
Recommended article: On the convex hull of random points in a polytope
Recommended article: Convex Hulls of Random Order Types
Recommended article: On a random convex hull in an n-ball
Recommended article: Random approximation and the vertex index of convex bodies
Recommended article: Random approximation of convex bodies
Recommended article: Random convex hulls: a variance revisited
Recommended article: An explicit formula about the convex hull of random points
Recommended article: EXPECTED MEAN WIDTH OF THE RANDOMIZED INTEGER CONVEX HULL
Recommended article: Computing the integer hull of convex polyhedral sets
description: scientific article; zbMATH DE number 2138090