Counting lattice points inside convex polyhedra

[Alastair Irving]

Hi All

I was wondering if sage implements any algorithm for counting the number
of points with integer coordinates inside polyhedra with rational
coordinates. even such an algorithm for polygons would be useful for me.

Best wishes

Alastair

[D. S. McNeil]

> I was wondering if sage implements any algorithm for counting the number of
> points with integer coordinates inside polyhedra with rational coordinates.
>  even such an algorithm for polygons would be useful for me.

Have a look at the integral_points method of Polyhedron objects, which
might do what you're looking for:

sage: P = Polyhedron([[1/2, 1/2], [1/2, 7/2], [7/2, 1/2], [7/2, 7/2]])
sage: P
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 4 vertices.

sage: P.integral_points()
[(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)]
sage: len(P.integral_points())
9

Note that this constructs the integral points rather than counts them,
so if there are lots of points in the enveloping lattice polytope it
won't be that fast, but maybe it'll work for your purposes.

Doug

--
Department of Earth Sciences
University of Hong Kong

[Volker Braun]

The integral_points method (which I wrote :-) uses PALP to enumerate the points. Eventually we should implement Barvinok's algorithm for counting lattice points. I think that this could be done in a few days, but I haven't actually done anything for it. But feel free to send a patch :-)

[Alastair Irving]

On 28/02/2011 13:19, D. S. McNeil wrote:
>> I was wondering if sage implements any algorithm for counting the number of
>> points with integer coordinates inside polyhedra with rational coordinates.
>> even such an algorithm for polygons would be useful for me.
>
> Have a look at the integral_points method of Polyhedron objects, which
> might do what you're looking for:

Yes it does. Thank you.

Alastair