Rainbow polygons for colored point sets in the plane

Abstract

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 $rb-index(S)$ denote the smallest size of a perfect rainbow polygon for a colored point set $S$, and let $rb-index(k)$ be the maximum of $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 $rb-index(k)$ vertices. In this paper, we determine the values of $rb-index(k)$ up to $k=7$, which is the first case where $rb-index(k)\ne k$, and we prove that for $k\ge 5$, \[ \frac{40\lfloor (k-1)/2 \rfloor -8}{19} %Birgit: \leq\operatorname{rb-index}(k)\leq 10 \bigg\lfloor\frac{k}{7}\bigg\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$ vertices can be computed in $O(n\log n)$ time.

23 pages, 11 figures, to appear at Discrete Mathematics

References in corpus (2)

• Balanced partitions of 3-colored geometric sets in the plane
• Dynamic Planar Convex Hull