On $k$-Gons and $k$-Holes in Point Sets
Oswin Aichholzer, Ruy Fabila‐Monroy, Hernàn González-Aguilar, Thomas Hackl, Marco A. Heredia, Clemens Huemer, Jorge Urrutia, Pável Valtr, Birgit Vogtenhuber · arXiv (Cornell University) · 2014
We consider a variation of the classical Erdős-Szekeres problems on the existence and number of convex $k$-gons and $k$-holes (empty $k$-gons) in a set of $n$ points in the plane. Allowing the $k$-gons to be non-convex, we show bounds and structural results on maximizing and minimizing their numbers. Most noteworthy, for any $k$ and sufficiently large $n$, we give a quadratic lower bound for the number of $k$-holes, and show that this number is maximized by sets in convex position.