0
$\begingroup$

Is there a connections between the number of vertices and the number of lattice points of $P_I$, the integer hull of a polytope $P$? Which is usually more difficult to determine? Or if I have a bound on the number of vertices, can I also bound the number of lattice points?

Is counting the number of vertices or lattice points equivalent or easier (in terms of algorithmic complexity) than determining them?

$\endgroup$

1 Answer 1

1
$\begingroup$

In response to your first question the number of vertices does not control the number of lattice points. Consider the polytopes $P=conv[(1,1),(1,-1),(-1,-1),(-1,1)]$, and $Q=conv[(0,1),(2,-1),(-2,-1)]$. They have the same number of lattice points but different number of vertices.

In regard to your second question it is easier to determine the vertices since these just come down to finding solutions to the defining hyperplanes (since you are not defining your polytope as the convex hull of a set of vertices I am assuming you are starting with the hyperplanes).

For your third question, there is clearly no bound as you could always take a scalar multiple of your polytope to get more lattice points.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.