Almost Empty Monochromatic Polygons in Planar Point Sets

Abstract

For integers $r\ge 3$, $c\ge 2$, and $s\ge 0$, let ${\mathsf{M}}_r^{\star }(c,s)$ denote the smallest integer such that any set of at least ${\mathsf{M}}_r^{\star }(c,s)$ points in the plane in general position (no three on a line), colored with $c$ colors, contains a monochromatic $r$-gon (not necessarily convex) with at most $s$ interior points. Define ${\lambda }_r^{\star }(c)$ to be the smallest integer such that ${\mathsf{M}}_r^{\star }(c,{\lambda }_r^{\star }(c))<\infty$. The case of triangles, that is, $r=3$, has been studied in recent years. In this paper, we establish bounds on ${\lambda }_r^{\star }(c)$, for $r\ge 4$. Specifically, in the bichromatic case, we prove that ${\lambda }_r^{\star }(2)\le \lfloor \frac{r-2}{2}\rfloor$, for every $r\ge 3$. For hexagons, we sharpen this bound to ${\lambda }_6^{\star }(2)\le 1$, that is, every sufficiently large bichromatic planar point set in general position contains a monochromatic hexagon with at most one interior point. Next, for any number of colors $c\ge 3$ and $r\ge 3$, we show that $$(r-2)\lfloor \frac{c-1}{2}\rfloor \le {\lambda }_r^{\star }(c)\le (r-2)(c-2)+\lfloor (r-2){\delta }_c\rfloor ,$$ for some constant ${\delta }_c\in (0,\frac{1}{2}]$, depending on $c$. The upper bounds combine spiral polygonizations with nested convex-hull arguments and, in the hexagon case, incidence counting in $4$-connected triangulations. The lower bounds follow from colored Horton-set constructions.

arXiv comment28 pages, 9 figures