Rainbow polygons for colored point sets in the plane *
Résumé
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.
* A preliminary version was presented at the 18th Spanish Meeting on Computational Geometry (2019).
Domaines
Mathématiques [math]
Fichier principal
Flores-Peñaloza et al. - 2021 - Rainbow polygons for colored point sets in the pla.pdf (1.63 Mo)
Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)