Perfect Rainbow Polygons for Colored Point Sets in the Plane

EasyChair Preprint no. 2980

4 pagesDate: March 17, 2020

Abstract

Given a planar $n$-colored point set $S= S_1 \cup \ldots \cup S_n$ in general position, a simple polygon $P$ is called a \emph{perfect rainbow} polygon if it contains exactly one point of each color. The \emph{rainbow index} $r_n$ is the minimum integer $m$ such that every $n$-colored point set $S$ has a perfect rainbow polygon with at most $m$ vertices. We determine the values of $r_n$ for $n \leq 7$, and prove that in general $\frac{20n-28}{19} \leq r_n \leq \frac{10n}{7} + 11$.

Keyphrases: colored point sets, covering, polygon