Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
"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). –  Gabor Retvari Nov 25 '12 at 23:18

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.