2
$\begingroup$

Note, a polyhedron is the intersection of finitely many half spaces in $\mathbb{R}^n$ and a polytope is a bounded polyhedron.

Let $M$ be an $m \times n$ matrix of integers. Let $P$ be the (possibly unbounded) polyhedron in $\mathbb{R}^n$ given by $$M \cdot v \geq 0 \quad \textrm{and} \quad v \geq 0.$$ Clearly $0 \in P$ and $P$ is bounded iff $P = \{0\}$. By solving a linear programming problem we can determine if $0$ is the only point in $P$, and so if $P$ is a polytope. Doing this takes $O(m^n)$. Is there a faster way to determine if $P$ is actually a polytope?

$\endgroup$
  • $\begingroup$ "Doing this takes $O(m^n)$." Are you sure about this? Linear programs can be solved in time that is polynomial in $m$ and $n$ (see, e.g., the ellipsoid algorithm). $\endgroup$ – Gabor Retvari Nov 25 '12 at 23:18

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.