Ask Your Question
1

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

asked 2021-08-10 19:52:09 +0100

Justin McClung gravatar image

updated 2024-12-18 20:26:14 +0100

FrédéricC gravatar image

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 flag offensive close merge delete

1 Answer

Sort by » oldest newest most voted
1

answered 2021-08-14 11:21:49 +0100

slelievre gravatar image

updated 2021-08-14 11:45:26 +0100

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".

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2021-08-10 19:52:09 +0100

Seen: 676 times

Last updated: Aug 14 '21