The definition of a polyhedron is any $x$ such that $Ax \geq b, A \in \mathbb{R}^{m\times n}, b \in \mathbb{R}^n$. A half space is defined as $a'x \geq b \text{ where } a,x \in \mathbb{R}^n ,b\in \mathbb{R}$.

So, can a halfspace be called a polyhedron where $m=1$?

(It won't be a polytope though, right?)

  • $\begingroup$ As far as I know, "polytope" is the general concept for arbitary dimensions, and "polyhedron" and "polygon" are its specializations to 3 and 2 dimensions. "Polyhedra" is the plural of "polyhedron"; "a polyhedra" is a grammatical error. $\endgroup$ – hmakholm left over Monica Oct 13 '12 at 18:32
  • $\begingroup$ @HenningMakholm, I fixed the plural error but I don't think polyhedron are only 3 dimensions. My book explicitly states polyhedrons of n dimensions. $\endgroup$ – Inquest Oct 13 '12 at 18:36
  • $\begingroup$ I don't think that's standard terminology in geometry. For that matter, I don't think allowing a "polyhedron" to be unbounded is standard in geometry, nor is it standard to require of a general "polyhedron" that it is convex. But these conventions may well be common in other areas of mathematics; for example I suppose they are more or less what one wants to speak about in optimization theory. $\endgroup$ – hmakholm left over Monica Oct 13 '12 at 18:48
  • $\begingroup$ I am reading a book on Simplex Method. $\endgroup$ – Inquest Oct 13 '12 at 19:00
  • $\begingroup$ x @Inquest: Yes, that is optimization theory. $\endgroup$ – hmakholm left over Monica Oct 13 '12 at 19:01

The words polygon and polyhedron have been defined in many different ways. There really is no fully standard usage of the terms polyhedron and polytope, however, usually, polytope is more restrictive. Coxeter used the term polytope and later there were books by Grünbaum (Convex Polytopes) and Ziegler (Lectures on Polytopes). One approach to a definition of a polytope is to take the convex hull of a finite number of points and another approach is to take the bounded intersection of half-spaces. However, the spirit of what these two authors have tried to do is to restrict polytopes to objects which are convex, closed and bounded, and with "flat faces." Some linear programming books allow unbounded feasible regions for linear programming situations but the interesting cases for applications typically involve bounded feasible regions.

  • $\begingroup$ Joseph, that's an interesting comment. And you led me to discover some really good books but I'm still confused about my question, I agree that in practice, one will rarely find unbounded feasible regions but would a halfspace as such be a polyhedron in the scope of optimization? $\endgroup$ – Inquest Oct 15 '12 at 15:53
  • $\begingroup$ @Inquest Arrangements of lines, arrangements of hyperplanes, polytopes, polyhedra, polyhedral cones, and pointed polyhedra are all interesting mathematical objects and have been studied by mathematicians because they show interesting properties. In optimization problems one typically needs a way to single out some set of points as being special- optimal from some point of view. So while there may be some definitions of polyhedron that allow a polyhedron to consist of a single half-space this would be "artificial." $\endgroup$ – Joseph Malkevitch Oct 17 '12 at 20:12

Your Answer

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

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