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.

In the book Introduction to Linear Optimization by Bertsimas Dimitri, a polyhedron is defined as a set $ \lbrace x \in \mathbb{R^n} | Ax \geq b \rbrace $, where A is an m x n matrix and b is a vector in $\mathbb{R^m}$. What it means is that a polyhedron is the intersection of several halfspaces.

A ball can also be viewed as the intersection of infinitely many halfspaces. So I was wondering if a ball is also a polyhedron by that definition or by any other definition that you might use?

Thanks and regards!

share|improve this question
    
Can someone explain how a sphere can be viewed as the intersection of infinite halfspaces? –  Cam Sep 17 '10 at 20:57
    
The wording is slightly wrong. I took it to mean: "The ball can be viewed as the intersection of infinitely many halfspaces." –  alext87 Sep 17 '10 at 21:00
    
Thanks! Corrected it. –  Tim Sep 17 '10 at 21:59
    
Technically yes with some non-Euclidean norms like $L_1$ and $L_{\infty}$. For example in the metric space $(\mathbb R^2,L_1)$, the unit ball is the convex hull of $(1,0), (0,1), (-1,0), (0,-1)$. In $(\mathbb R^2,L_{\infty})$, the unit ball is the square $[-1,1]\times[-1,1]$. These remain polytopes for all finite dimensions $ n \to \mathbb R^n$ –  alancalvitti Jan 15 '13 at 16:59
add comment

3 Answers

up vote 3 down vote accepted

No a ball is not a polyhedron, even by this definition. In your definition the matrix $A$ is of size $m\times n$, where $m\in\mathbb{N}$ thus the matrix is finite. The integer $m$ is an upper bound on the number of halfspaces which intersect to form the polyhedron.

The reason $m$ is an upper bound is because suppose $A$ has two rows identical. Then there are two hyperspaces which are parallel so at least one of them does not form any part of the polyhedron.

share|improve this answer
add comment

The usual definition of a polyhedron requires that either one intersects a finite number of half-spaces, or one takes the convex hull of a finite set of points.

See the book Convex Polytopes by Branko Grünbaum (either the first or second edition).

share|improve this answer
    
Thanks! Are the two definitions equivalent? –  Tim Sep 17 '10 at 23:01
1  
@Tim: The two definitions are not equivalent; consider a halfspace. They are equivalent if the shape is bounded, and this equivalence is a fundamental result in the theory of convex polytopes. It can be proved by the Fourier-Motzkin elimination. –  Tsuyoshi Ito Sep 18 '10 at 11:05
add comment

polyhedron is not ball cause its a solid figure bounded by plane polygons or faces

share|improve this answer
3  
An potential answer would begin "a ball is not a polyhedron because..." and not the other way around. I can see you have the beginnings of an answer, but work a little on retyping it and it may get some attention. –  rschwieb Jan 15 '13 at 16:46
add comment

Your Answer

 
discard

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

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