Is a ball a polyhedron?

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!

• 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
• 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

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.

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

• Thanks! Are the two definitions equivalent? – Tim Sep 17 '10 at 23:01
• @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

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

• 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