Extended formulations for polygons

Understand

The extension complexity of a polytope $P$ is the smallest integer $k$ such that $P$ is the projection of a polytope $Q$ with $k$ facets.

• We study the extension complexity of $n$-gons in the plane.
• First, we give a new proof that the extension complexity of regular $n$-gons is $O(\log n)$, a result originating from work by Ben-Tal and Nemirovski (2001).
• Our proof easily generalizes to other permutahedra and simplifies proofs of recent results by Goemans (2009), and Kaibel and Pashkovich (2011).