11
$\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$
17
$\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$
  • $\begingroup$ Thanks for the counterexample. Does requiring $P$ to be facet-transitive and vertex-transitive have an effect? $\endgroup$ – Pedro Ruiz Jan 20 '17 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 '17 at 21:21
13
$\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)$.

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

enter image description here

$\endgroup$
10
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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