polytope, projection, extension complexity, convex polygon


Extension complexity of (convex) polygons ★★

Author(s):

The extension complexity of a polytope $P$ is the minimum number $q$ for which there exists a polytope $Q$ with $q$ facets and an affine mapping $\pi$ with $\pi(Q) = P$.

\begin{question} Does there exists, for infinitely many integers $n$, a convex polygon on $n$ vertices whose extension complexity is $\Omega(n)$? \end{question}

Keywords: polytope, projection, extension complexity, convex polygon

Syndicate content