15
$\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
    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
    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$ 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
    Sep 4, 2021 at 6:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.