1
$\begingroup$

I am using Python but I wouldn't mind changing language. All I have gotten from my research are tools to count the number of (lattice) points inside a region given the equations for the planes that enclose it. Other tools are made to optimize a given function inside the polytope (linear programming).

How about finding the lattice points alone? For example, a function of the kind

latticePoints( 'x < 5 & x > 0' ) = [ 1, 2, 3, 4]

Plus I am looking for something to work in the multivariate scenario (constrains on x, y, z, ...).

I am currently trying to solve this using ppl.

$\endgroup$
  • 1
    $\begingroup$ Do you want to decide whether there exist integer points inside a given polytope, or do you want to enumerate all integer points inside a given polytope? $\endgroup$ – Rodrigo de Azevedo Jan 18 '18 at 11:16
  • 1
    $\begingroup$ Is the polyhedron convex? $\endgroup$ – rchilton1980 Jan 18 '18 at 13:36
  • $\begingroup$ @RodrigodeAzevedo The goal in to enumerate the points. $\endgroup$ – Vinícius Godim Jan 18 '18 at 17:24
  • $\begingroup$ @rchilton1980 Yes it is convex. $\endgroup$ – Vinícius Godim Jan 18 '18 at 17:25
  • 3
    $\begingroup$ Since convex, checking if a given point is inside/outside is I think straightforward (p is inside iff it's "below" each outwardly-oriented hyperplane). Enumerating all such points to test is maybe less straightforward, esp in high dimensions. Do you have suitable bounds on the coordinates? If you can make an aligned bounding "box", then you can enumerate all the points in that box, check each against the polyhedron, and only record/output the ones that pass the inside/outside check. $\endgroup$ – rchilton1980 Jan 18 '18 at 17:35

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.