Perfect rainbow polygons for colored point sets in the plane

David Flores-Peñaloza, Mikio Kano, Leonardo Martínez-Sandoval, David Orden, Javier Tejel, Csaba D. Tóth, Jorge Urrutia, Birgit Vogtenhuber

Research output: Chapter in Book/Report/Conference proceedingConference paperpeer-review


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 perfect rainbow polygon if it contains exactly one point of each color. The 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 $20n-2819 leq r_n leq 10n7 + 11$.
Original languageEnglish
Title of host publicationProc. XVIII Encuentros de Geometría Computacional
Place of PublicationGirona, Spain
Number of pages4
Publication statusPublished - 2019

Cite this