Rainbow polygons for colored point sets in the plane

Given a colored point set in the plane, a perfect rainbow polygon is a simple polygon that contains exactly one point of each color, either in its interior or on its boundary. Let $\mathrm{rb-index}(S)$ denote the smallest size of a perfect rainbow polygon for a colored point set $S$, and let $\mathrm{rb-index}(k)$ be the maximum of $\mathrm{rb-index}(S)$ over all $k$-colored point sets in general position; that is, every $k$-colored point set $S$ has a perfect rainbow polygon with at most $\mathrm{rb-index}(k)$ vertices. In this paper, we determine the values of $\mathrm{rb-index}(k)$ up to $k=7$, which is the first case where $\mathrm{rb-index}(k)\mathrm{\ne }k$, and we prove that for $k\ge 5$, $$\frac{40\lfloor (k-1)\mathrm{/}2\rfloor -8}{19}\le \mathrm{rb-index}(k)\le 10\lfloor \frac{k}{7}\rfloor +11.$$ Furthermore, for a $k$-colored set of $n$ points in the plane in general position, a perfect rainbow polygon with at most $10 \lfloor\frac{k}{7}\rfloor

• 11$verticescanbecomputedin$O(n\log n)$ time.