Integer points in convex polyhedra
The study of integer points in convex polyhedra
The set of integer points, or, more generally, the set of points of an
Properties
For a lattice Λ, Minkowski's theorem relates the number d(Λ) (the volume of a fundamental parallelepiped of the lattice) and the volume of a given symmetric convex set S to the number of lattice points contained in S.
The number of lattice points contained in a polytope all of whose vertices are elements of the lattice is described by the polytope's Ehrhart polynomial. Formulas for some of the coefficients of this polynomial involve d(Λ) as well.
Applications
Loop optimization
In certain approaches to loop optimization, the set of the executions of the loop body is viewed as the set of integer points in a polyhedron defined by loop constraints.
See also
- Convex lattice polytope
- Pick's theorem
References and notes
- ^ In some contexts convex polyhedra are called simply "polyhedra".
- ^ Integer points in polyhedra. Geometry, Number Theory, Representation Theory, Algebra, Optimization, Statistics, ACM--SIAM Joint Summer Research Conference, 2006
- convex lattice polytope, the convex hullof finitely many points in an affine lattice.
- ISBN 1-4200-4382-X, p.15-7