5
$\begingroup$

Consider a (not necessarily bounded) convex polyhedron $P\subset \mathbb{R}^n$ which has $k$ facets. Let $L:\mathbb{R}^n \to \mathbb{R}^m$ be a linear transformation.

Question1: Is there a fixed constant $C$ such that the number of facets of $L(P)$ is bounded by $Ck$ ?

Edit:

Question2: Is there any bound on the number of facets of $L(P)$ in terms of $P$?

Question3: Is there any bound on the number of (none geometrical redundant) half-spaces which defined $L(P)$ in terms of $P$?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

No. Every bounded convex polyhedron $Q$ with $v$ vertices is an image of a simplex $P$ with $v$ vertices and $v$ facets by a linear transformation. However, $Q$ may have many facets. For example, the cross-polytopes (dual to hypercubes) have $2d$ vertices and $2^d$ facets, one for each orthant, and $2^d$ is not $O(d)$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks. Is there any bound on the number of facets of $L(P)$ in terms of $P$? $\endgroup$
    – Mahdi - Free Palestine
    Commented Jul 1, 2014 at 8:47
  • $\begingroup$ @Mahdi: Yes. For example, cyclic polytopes have the most facets as a function of the number of vertices. There are some easy weaker bounds. So, the number of vertices of $P$ gives you a bound on the number of facets of any linear image of $P$. $\endgroup$
    – Douglas Zare
    Commented Jul 1, 2014 at 9:00
  • $\begingroup$ But, you claim is not true for an unbounded polyhedron. For example, consider a polyhedron cone. $\endgroup$
    – Mahdi - Free Palestine
    Commented Jul 1, 2014 at 9:19
  • $\begingroup$ @Mahdi: You can use a projective transformation switching the hyperplane at infinity with a hyperplane not intersecting the polyhedron. Are you saying more than that counting the vertices in affine space might miss vertices at infinity? $\endgroup$
    – Douglas Zare
    Commented Jul 1, 2014 at 11:40

You must log in to answer this question.

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