Download PDFOpen PDF in browserPerfect Rainbow Polygons for Colored Point Sets in the PlaneEasyChair Preprint 29804 pages•Date: March 16, 2020AbstractGiven 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
|