On the Largest Convexity Number of Co-Finite Sets in the Plane

Abstract

The convexity number of a set $X\subset {\mathbb{R}}^2$ is the minimum number of convex subsets required to cover it. We study the following question: what is the largest possible convexity number $f(n)$ of ${\mathbb{R}}^2\setminus S$, where $S$ is a set of $n$ points in general position in the plane? We prove that for all $n\ge 4$, $\lfloor \frac{n+5}{2}\rfloor \le f(n)\le \frac{7n+44}{11}$. We also show that for every $n\ge 4$, if the points of $S$ are in convex position then the convexity number of ${\mathbb{R}}^2\setminus S$ is $\lfloor \frac{n+5}{2}\rfloor$. This solves a problem of Lawrence and Morris [Finite sets as complements of finite unions of convex sets, Disc. Comput. Geom. 42 (2009), 206-218].

15 pages, 13 figures