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.

Improve this question
$\endgroup$
9
  • $\begingroup$ by face you mean a face of codimension 1? $\endgroup$
    – Fedor Petrov
    Commented Jul 21, 2017 at 17:14
  • $\begingroup$ Yes, of dimension n-1 $\endgroup$
    – makkostya
    Commented 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$
    – Fedor Petrov
    Commented 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$
    – Aaron Meyerowitz
    Commented 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$
    – Tobias Fritz
    Commented Jul 23, 2017 at 21:40

1 Answer 1

Reset to default
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

Improve this answer
$\endgroup$

You must log in to answer this question.

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