16
$\begingroup$

Let $P$ be a convex polytope in $\mathbb{R}^d$ with $n$ vertices and $f$ facets. Let $\text{Proj}(P)$ denote the projection of $P$ into $\mathbb{R}^2$.

Can $\text{Proj}(P)$ have more than $f$ facets?

In the general case, each successive projection can increase the number of facets from $f$ to $\left\lfloor \frac{f^2}{2} \right\rfloor$, but I'm wondering if $\mathbb{R}^2$ is a special case.

$\endgroup$

3 Answers 3

25
$\begingroup$

Consider the polytope in $\mathbb{R}^3$ with $8$ vertices at coordinates $(\pm 1, \pm 2, 1), (\pm 2, \pm 1, -1)$. Geometrically this looks like a cube where the top face is stretched in the direction of the $y$-axis and the bottom face is stretched in the direction of the $x$-axis, but it still has the face structure of a cube and in particular has $6$ facets.

It's projection onto the first two coordinates is clearly an octagon, and hence has two more facets than the original polytope.

$\endgroup$
3
  • $\begingroup$ Thanks for the counterexample. Does requiring $P$ to be facet-transitive and vertex-transitive have an effect? $\endgroup$
    – Pedro Ruiz
    Commented Jan 20, 2017 at 19:05
  • $\begingroup$ That I'm not sure about. I'll note that that example is vertex transitive (but not facet transitive). I will say that this does hold for all regular (i.e. flag transitive) polytopes, with the possible exception of the 120-cell, which is unlikely but I don't want to take the time to analyze it. $\endgroup$
    – Nate
    Commented Jan 20, 2017 at 21:21
  • $\begingroup$ So more generally, the analogous deformed prism with base an n-gon shows that one can obtain a 2n-gon as a projection of a polyhedron with n+2 facets. $\endgroup$ Commented Sep 4, 2021 at 6:01
25
$\begingroup$

Your question is essentially about extension complexity. In general, the extension complexity of a polytope $P$ is the minimum number of facets over all polytopes $Q$ which project to $P$. You are interested in the extension complexity of polygons. Fiorini, Rothvoß, and Tiwary proved that regular $n$-gons have extension complexity $O(\log n)$. For lower bounds, they give examples of $n$-gons which have extension complexity $\sqrt{2n}$.

It is an open question if there exists for infinitely many $n$, an $n$-gon with extension complexity $\Omega(n)$. Edit. Shitov has recently shown that every convex $n$-gon has extension complexity at most $147 n^{2/3}$, which resolves the open question in the negative.

As a bonus, here is a picture of the polytope in Nate's answer (courtesy of Samuel Fiorini).

enter image description here

$\endgroup$
16
$\begingroup$

Another, combinatorially minimal, counterexample of such a polytope $P$ (with only five facets) is the convex hull of the six vertices $(\pm2, 0, 0)$, $(\pm1, \pm1, 1)$. Its projection to the $xy$-plane is a hexagon. The minimality of the number of vertices and the number of facets is easy to prove.

$\endgroup$
1
  • 1
    $\begingroup$ --------------- ---- Nice! ---- --------------- $\endgroup$
    – Wlod AA
    Commented Sep 4, 2021 at 6:51

You must log in to answer this question.

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