7
$\begingroup$

Consider an $n$-dimensional convex polytope with $k$ vertices. In the worst case the number of faces is exponential in $n$ and $k$. Consider a $2$-dimensional plane which intersects this polytope, i.e., it intersects only a subset of all faces. Can I bound the number of such intersected faces? In the worst case, will this number be a polynomial in $n$ and $k$ or still exponential?

Thanks in advance.

$\endgroup$
  • $\begingroup$ by face you mean a face of codimension 1? $\endgroup$ – Fedor Petrov Jul 21 '17 at 17:14
  • $\begingroup$ Yes, of dimension n-1 $\endgroup$ – makkostya Jul 21 '17 at 17:21
  • 1
    $\begingroup$ Also, you mean bound via $k$ for fixed $n$ or for $n$ varying with $k$? In the first case it is not true that the number of faces may be exponential. $\endgroup$ – Fedor Petrov Jul 21 '17 at 17:29
  • 1
    $\begingroup$ For $n=2$ there are less than $2k$ faces. If you put a short pentagonal pyramid on each face of a dodecahedron you have $k=32$ and $60$ faces. That is probably the closest to $2$ that the ratio gets. $\endgroup$ – Aaron Meyerowitz Jul 22 '17 at 23:42
  • 1
    $\begingroup$ For the purposes of visualization, it may be easier to consider the dual question. I haven't thought about this in detail, but perhaps it is this one: for an $n$-polytope with $k$ facets, what is the maximal number of vertices that a $2$-dimensional projection can have? $\endgroup$ – Tobias Fritz Jul 23 '17 at 21:40
2
$\begingroup$

I found a paper wich shows that in the worst case it still can be exponential: "Shadows and slices of polytopes, Nina Amenta et al., 1996" https://dl.acm.org/citation.cfm?id=237228

$\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.