6

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!

Tim
  • 47,382
  • 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
  • 2
    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

4 Answers4

4

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

Joseph Malkevitch
  • 5,035
  • 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
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.

alext87
  • 2,879
2

Case $n=1$

When $n=1$ the ball is a segment and it is indeed a polyhedron.

Case $n=2$

Assume that the circle is a polyhedron. Think of the condition $A\mathbb{x}\ge\mathbb{b}$ as a system of linear inequalities, each of them defining a line and an associated halfplane. Since there is only a finite number of lines, there must exist $(x_0,y_0)$ such that $x_0^2 + y_0^2 = 1$ which is not in any of these lines. In particular $(x_0,y_0)$ would satisfy all the inequalities with $``>"$ rather than $``="$. This is a contradiction because, by continuity, $(x_0,y_0)$ would belong in the interior of the circle.

Case $n>2$

Define $h\colon\mathbb{R}^2\to\mathbb{R}^n$ by $h(x,y)=(x,y,0,\dots,0)$. The pre-image by $h$ of the ball in $\mathbb{R}^n$ is the circle. And since the pre-image of a polyhedron by an affine transformation is a polyhendron, we conclude that the $n$-dimensional ball cannot be a polyhedron either.

Leandro Caniglia
  • 1,880
-5

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

CLAYTON
  • 1
  • 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. – rschwieb Jan 15 '13 at 16:46