# how do I enumerate the integer lattice points contained in a convex polyhedron?

The following Sage code is working perfectly. It generates the polyhedron from a vertex list of interest and computes the Ehrhart polynomial.

p = Polyhedron(vertices = vertex_list)
p = p.ehrhart_polynomial(engine = 'latte')


How can I now compute the number of integer lattice points inisde the convex hull of the polyhedron? Moreover, can I enumerate them?

edit retag close merge delete

Sort by » oldest newest most voted

The Ehrhart polynomial $p$ of a polyhedron $P$ helps counting integral points in its dilates.

Indeed, for each integer $n$, the number of integral points in the dilate $n P$ is given by $p(n)$.

Sage also provides a direct method for counting integral points.

Here is an illustration.

Construct a polyhedron:

sage: vertex_list = [(0, 0, 1), (1, 0, 0), (1, 0, 1),
....:                (1, 1, 0), (1, 1, 1), (2, 1, 0)]
sage: P = Polyhedron(vertices=vertex_list)


Inspect it:

sage: P
A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 6 vertices


Find its Ehrhart polynomial via latte (requires installing the optional package latte_int):

sage: p = P.ehrhart_polynomial(engine='latte')
sage: p
2/3*t^3 + 2*t^2 + 7/3*t + 1


Get the number of integral points in the polyhedron via the Ehrhart polynomial:

sage: p(1)
6


Get the number of integral points in the polyhedron directly:

sage: P.integral_points_count()
6


Besides counting integral points, one can also be interested in finding these points explicitly.

The method integral_points provides that:

sage: points = P.integral_points()
sage: points
((1, 0, 0), (0, 0, 1), (1, 0, 1), (1, 1, 0), (2, 1, 0), (1, 1, 1))


The documentation for the ehrhart polynomial method gives hints about all that.

To access it in text mode, use a question mark:

sage: P.ehrhart_polynomial?


The documentation can also be browsed rendered in html:

sage: browse_sage_doc(P.ehrhart_polynomial)


To access the corresponding source code:

sage: P.ehrhart_polynomial??


To discover the integral_points_count and integral_points methods, use tab-completion:

sage: P.int<TAB>


where <TAB> means "press the TAB key on the keyboard".

more