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

DOI10.1007/S13366-011-0028-8zbMATH Open1236.52011arXiv1003.4365OpenAlexW2030141596MaRDI QIDQ664191FDOQ664191

Authors: Gennadiy Averkov, Christian Wagner 

Publication date: 29 February 2012

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

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.

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

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

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)

Cites Work

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

Cited In (14)

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

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)