Inequalities for the lattice width of lattice-free convex sets in the plane

DOI10.1007/S13366-011-0028-8MaRDI QIDQ664191zbMATH OpenOpenAlexFDO

Authors Gennadiy Averkov, Christian Wagner

Publication date 29 February 2012

Published in Beiträge zur Algebra und Geometrie (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1003.4365

zbMATH Keywords

arealattice widthconvex setinhomogeneous minimumcovering minimumlattice-free body

Mathematics Subject Classification ID

Length, area, volume and convex sets (aspects of convex geometry) (52A38) Inequalities and extremum problems involving convexity in convex geometry (52A40) Lattices and convex bodies in (2) dimensions (aspects of discrete geometry) (52C05) Packing and covering in (2) dimensions (aspects of discrete geometry) (52C15)

Abstract: A closed, convex set $K$ in $mathbb{R}^2$ with non-empty interior is called lattice-free if the interior of $K$ is disjoint with $mathbb{Z}^2$. In this paper we study the relation between the area and the lattice width of a planar lattice-free convex set in the general and centrally symmetric case. A correspondence between lattice width on the one hand and covering minima on the other, allows us to reformulate our results in terms of covering minima introduced by Kannan and Lov'asz. We obtain a sharp upper bound for the area for any given value of the lattice width. The lattice-free convex sets satisfying the upper bound are characterized. Lower bounds are studied as well. Parts of our results are applied in a paper by the authors and Weismantel for cutting plane generation in mixed integer linear optimization, which was the original inducement for this paper. We further rectify a result of Kannan and Lov'asz with a new proof.

Recommendations

• An analysis of mixed integer linear sets based on lattice point free convex sets
• Some covering problems for general planar lattices
• Width-diameter relations for planar convex sets with lattice point constraints
• Maximal lattice-free polyhedra: finiteness and an explicit description in dimension three
• Area-diameter and area-width relations for covering plane sets

Cites work

• scientific article; zbMATH DE number 3155900 (Why is no real title available?)
• scientific article; zbMATH DE number 3987367 (Why is no real title available?)
• scientific article; zbMATH DE number 3469632 (Why is no real title available?)
• scientific article; zbMATH DE number 3046578 (Why is no real title available?)
• A Minkowski-type theorem for covering minima in the plane
• Blowing up convex sets in the plane
• Convex and Discrete Geometry
• Covering minima and lattice-point-free convex bodies
• Der zentralsymmetrische Kern und die zentralsymmetrische Hülle von konvexen Körpern
• Maximal lattice-free convex sets in linear subspaces
• Maximal lattice-free polyhedra: finiteness and an explicit description in dimension three
• Successive-minima-type inequalities
• Two row mixed-integer cuts via lifting

Cited in

(13)

• Computing the covering radius of a polytope with an application to lonely runners
• Width-diameter relations for planar convex sets with lattice point constraints
• A probabilistic comparison of the strength of split, triangle, and quadrilateral cuts
• Hollow polytopes of large width
• A covering problem for plane lattices
• A local maximizer for lattice width of 3-dimensional hollow bodies
• Lattice-free simplices with lattice width \(2d - o(d)\)
• Homometry and direct-sum decompositions of lattice-convex sets
• An extremal property of lattice polygons
• On finitely generated closures in the theory of cutting planes
• On densities of lattice arrangements intersecting every \(i\)-dimensional affine subspace
• Complexity of linear relaxations in integer programming
• A proof of Lovász's theorem on maximal lattice-free sets

This page was built for publication: Inequalities for the lattice width of lattice-free convex sets in the plane

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q664191)