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 ) ≠ k , and we prove that for k ≥ 5 , 40 ⌊ ( k − 1 ) ∕ 2 ⌋ − 8 19 ≤ rb-index ( k ) ≤ 10 ⌊ k 7 ⌋ + 11 . Furthermore, for a k -colored set of n points in the plane in general position, a perfect rainbow polygon with at most 10 ⌊ k 7 ⌋ + 11 vertices can be computed in O ( n log n ) time.