Perfect Rainbow Polygons for Colored Point Sets in the Plane

EasyChair Preprint no. 2980

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

@Booklet{EasyChair:2980,
  author = {David Flores-Peñaloza and Mikio Kano and Leonardo Martínez-Sandoval and David Orden and Javier Tejel and Csaba D. Tóth and Jorge Urrutia and Birgit Vogtenhuber},
  title = {Perfect Rainbow Polygons for Colored Point Sets in the Plane},
  howpublished = {EasyChair Preprint no. 2980},

  year = {EasyChair, 2020}}