Rainbow polygons for colored point sets in the plane
Preprint
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 $\operatorname{rb-index}(S)$ denote the smallest size of a perfect rainbow polygon for a colored point set $S$, and let $\operatorname{rb-index}(k)$ be the maximum of $\operatorname{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 $\operatorname{rb-index}(k)$ vertices. In this paper, we determine the values of $\operatorname{rb-index}(k)$ up to $k=7$, which is the first case where $\operatorname{rb-index}(k)\neq 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.
Keywords
All Related Versions
This publication has 31 references indexed in Scilit:
- Plane Bichromatic Trees of Low DegreeDiscrete & Computational Geometry, 2017
- Discrete and Computational Geometry and Graphs2014
- Covering Paths for Planar Point SetsDiscrete & Computational Geometry, 2013
- Colorful StripsGraphs and Combinatorics, 2011
- Computational Geometry2008
- Using the Borsuk–Ulam Theorem2008
- Discrete Geometry on Red and Blue Points in the Plane — A Survey —2003
- Balanced Convex Partitions of Measures in ℝ 2Graphs and Combinatorics, 2002
- Hardness of Set Cover with Intersection 12000
- Geometric Discrepancy1999