Given a polytope represented by $$Ax\leq b$$ where $A\in\Bbb Z^{m\times n}$, $x\in\Bbb Z^n$ and $b\in\Bbb Z^m$ with $N\geq 0$ number of integer points can we construct a polytope with $N+1$ integer points, $\leq m+c$ constraints and $\leq n+c$ dimensions at a fixed $c\geq0$ in $O(n+m)$ time? What is the best that is known?

Essentially something like this should work. Add an additional dimension $x_{n+1}$ and consider polytope $-1<x_1,\dots,x_n<1$ polytope with exactly one integer point at origin in $n$ dimensions. We want a polytope that at $x_{n+1}=1$ is the first polytope and at $x_{n+1}=0$ is second one. How does one formalize this projective construction by using only linear inequalities without using quadratic inequalities?

In more generality I was looking for an $O(m_1+m_2+n_1+n_2)$ time scheme to construct a polytope $\tilde A\tilde x\leq \tilde b$ with $N_1+N_2$ integer points from polytopes $A_ix_i\leq b_i$ where $A_i\in\Bbb Z^{m_i\times n_i}$, $x_i\in\Bbb Z^{n_i}$ and $b_i\in\Bbb Z^{m_i}$ with $N_i\geq 0$ number of integer points at $i\in\{1,2\}$?

It certainly looks like it could be done with mapping quadratic constraints to linear constraints. However how to go about it is unclear.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.