Almost empty polygons

From MaRDI portal





The well-known Erdős-Szekeres convex polygon theorem guarantees that any sufficiently large number of points in general position in the plane will contain \(n\) points in convex position: the vertex set of a convex \(n\)-gon. This led Erdős to the question whether this \(n\)-gon can even be chosen to be empty, but that turned out to be false: \textit{J. D. Horton} [Can. Math. Bull. 26, 482--484 (1983; Zbl 0521.52010)] constructed arbitrarily large sets without empty convex 7-gon. On the other hand, any set of at least \(n\) points contains an empty 5-gon, see \textit{H. Harborth} [Elem. Math. 33, 116--118 (1978; Zbl 0397.52005)], leaving only the empty 6-gon case open, see \textit{M. Overmars} [Discrete Comput. Geom. 29, 153--158 (2003; Zbl 1019.52010)]. In this paper, the emptyness restriction is relaxed. Thus we do not know whether every sufficiently large set contains an empty convex 6-gon, but the author shows that it does contain a 6-gon with at most five points in its interior. And in general, the author constructs arbitrary large sets without an \(n\)-gon containing at most \(k\) points in the interior for \(k\leq 2^{(n+6)/4} - n -3\).











This page was built for publication: Almost empty polygons

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4820754)