5
$\begingroup$

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!

  • 0
    Can someone explain how a sphere can be viewed as the intersection of infinite halfspaces?2010-09-17
  • 0
    The wording is slightly wrong. I took it to mean: "The ball can be viewed as the intersection of infinitely many halfspaces."2010-09-17
  • 1
    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$2013-01-15

3 Answers 3

3

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.

3

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

  • 0
    Thanks! Are the two definitions equivalent?2010-09-17
  • 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.2010-09-18
-3

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

  • 4
    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.2013-01-15