Point Sets with Small Integer Coordinates and with Small Convex Polygons

Abstract

In 1935, Erdős and Szekeres proved that every set of $n$ points in general position in the plane contains the vertices of a convex polygon of $\frac{1}{2}{\log }_2(n)$ vertices. In 1961, they constructed, for every positive integer $t$, a set of $n:=2^{t-2}$ points in general position in the plane, such that every convex polygon with vertices in this set has at most ${\log }_2(n)+1$ vertices. In this paper we show how to realize their construction in an integer grid of size $O(n^2{\log }_2(n{)}^3)$.

References in corpus (1)

• Drawing the Horton Set in an Integer Grid of Minimum Size