Name
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 not equal k, and we prove that for k >= 5,40 right perpendicular(k-1)/2 left perpendicular - 8/19 <= rb-index(k) <= right perpendicular k/7 left perpendicular + 11.Furthermore, for a k-colored set of n points sn the plane in general position, a perfect rainbow polygon with at most 10 right perpendicular k/7 left perpendicular + 11 vertices can be computed in O(n log n) time. (C) 2021 Elsevier B.V. All rights reserved. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1016/j.disc.2021.112406 | DISCRETE MATHEMATICS |
Keywords | DocType | Volume |
Colored point set, Enclosing simple polygon, Particular cases, General bounds | Journal | 344 |
Issue | ISSN | Citations |
7 | 0012-365X | 1 |
PageRank | References | Authors |
0.35 | 0 | 8 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| David Flores-Peñaloza | 1 | 1 | 0.69 |
| Mikio Kano | 2 | 548 | 99.79 |
| Leonardo Martínez-Sandoval | 3 | 1 | 0.35 |
| David Orden | 4 | 160 | 20.26 |
| Javier Tejel | 5 | 90 | 13.60 |
| Csaba D. Toth | 6 | 91 | 13.63 |
| Jorge Urrutia | 7 | 1064 | 134.74 |
| Birgit Vogtenhuber | 8 | 127 | 27.19 |