  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). Second, we prove a lower
bound of $\sqrt{2n}$ on the extension complexity of generic $n$-gons. Finally,
we prove that there exist $n$-gons whose vertices lie on a $O(n) \times O(n^2)$
integer grid with extension complexity $\Omega(\sqrt{n}/\sqrt{\log n})$.

Discrete Mathematics;Computational Geometry;Combinatorics