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$
9
  • $\begingroup$ by face you mean a face of codimension 1? $\endgroup$ Jul 21, 2017 at 17:14
  • $\begingroup$ Yes, of dimension n-1 $\endgroup$
    – makkostya
    Jul 21, 2017 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$ Jul 21, 2017 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$ Jul 22, 2017 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$ Jul 23, 2017 at 21:40

1 Answer 1

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 and acknowledge you have read our privacy policy.

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