0
$\begingroup$

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?)

$\endgroup$
5
  • $\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, 2012 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, 2012 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, 2012 at 18:48
  • $\begingroup$ I am reading a book on Simplex Method. $\endgroup$
    – Inquest
    Oct 13, 2012 at 19:00
  • $\begingroup$ x @Inquest: Yes, that is optimization theory. $\endgroup$
    – hmakholm left over Monica
    Oct 13, 2012 at 19:01

1 Answer 1

Reset to default
2
$\begingroup$

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.

$\endgroup$
2
  • $\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, 2012 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, 2012 at 20:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .