×
Flores-Peñaloza, David; Kano, Mikio; Martínez-Sandoval, Leonardo; Orden, David; Tejel, Javier; Tóth, Csaba D.; Urrutia, Jorge; Vogtenhuber, Birgit

Rainbow polygons for colored point sets in the plane. (English) Zbl 1466.52007

Discrete Math. 344, No. 7, Article ID 112406, 16 p. (2021).
Summary: 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 \geq 5\), \[ \frac{ 40 \lfloor ( k - 1 ) / 2 \rfloor - 8}{ 19} \leq \operatorname{rb-index} ( k ) \leq 10 \left\lfloor \frac{ k}{ 7} \right\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.

Cited in 2 Reviews
Cited in 1 Document

MSC:

52A37 Other problems of combinatorial convexity
52C10 Erdős problems and related topics of discrete geometry
52A10 Convex sets in \(2\) dimensions (including convex curves)

Keywords:

colored point set; enclosing simple polygon; particular cases; general bounds
Cite Review PDF
Full Text: DOI arXiv
Creative Commons CC license icon Creative Commons BY license icon

References:

[1] Ábrego, Bernardo M.; Fernández-Merchant, Silvia; Kano, Mikio; Orden, David; Pérez-Lantero, Pablo; Seara, Carlos; Tejel, Javier, \( K_{1 , 3}\)-Covering red and blue points in the plane, Discrete Math. Theor. Comput. Sci., 21, 3, 6 (2019) · Zbl 1411.05062
[2] Abu-Affash, A. Karim; Carmi, Paz; Katz, Matthew J.; Trabelsi, Yohai, Bottleneck non-crossing matching in the plane, Comput. Geom., 47, 3, 447-457 (2014) · Zbl 1281.65025
[3] Aloupis, Greg; Cardinal, Jean; Collette, Sébastien; Demaine, Erik D.; Demaine, Martin L.; Dulieu, Muriel; Monroy, Ruy Fabila; Hart, Vi; Hurtado, Ferran; Langerman, Stefan; Saumell, Maria; Seara, Carlos; Taslakian, Perouz, Non-crossing matchings of points with geometric objects, Comput. Geom., 46, 1, 78-92 (2013) · Zbl 1254.65032
[4] Aloupis, Greg; Cardinal, Jean; Collette, Sébastien; Imahori, Shinji; Korman, Matias; Langerman, Stefan; Schwartz, Oded; Smorodinsky, Shakhar; Taslakian, Perouz, Colorful strips, Graphs Combin., 27, 3, 327-339 (2011) · Zbl 1235.05047
[5] Arkin, Esther M.; Mitchell, Joseph S. B.; Piatko, Christine D., Minimum-link watchman tours, Inform. Process. Lett., 86, 4, 203-207 (2003) · Zbl 1173.68757
[6] Barba, Luis; Schnider, Patrick, Sharing a pizza: Bisecting masses with two cuts, (Gudmundsson, Joachim; Smid, Michiel H. M., Proc. 29th Canadian Conference on Computational Geometry. Proc. 29th Canadian Conference on Computational Geometry, CCCG (2017)), 174-178, URL http://2017.cccg.ca/proceedings/CCCG2017.pdf
[7] Bereg, Sergey; Hurtado, Ferran; Kano, Mikio; Korman, Matias; Lara, Dolores; Seara, Carlos; Silveira, Rodrigo I.; Urrutia, Jorge; Verbeek, Kevin, Balanced partitions of 3-colored geometric sets in the plane, Discrete Appl. Math., 181, 21-32 (2015) · Zbl 1304.05008
[8] Bereg, Sergey; Kano, Mikio, Balanced line for a 3-colored point set in the plane, Electron. J. Combin., 19, 1, P33 (2012), URL http://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i1p33 · Zbl 1246.52011
[9] Bereg, Sergey; Ma, Feifei; Wang, Wencheng; Zhang, Jian; Zhu, Binhai, On some matching problems under the color-spanning model, Theoret. Comput. Sci., 786, 26-31 (2019) · Zbl 1429.68318
[10] de Berg, Mark; Cheong, Otfried; van Kreveld, Marc; Overmars, Mark, Computational Geometry: Algorithms and Applications (2008), Springer: Springer Berlin · Zbl 1140.68069
[11] Bespamyatnikh, Sergei; Kirkpatrick, David G.; Snoeyink, Jack, Generalizing ham sandwich cuts to equitable subdivisions, Discrete Comput. Geom., 24, 4, 605-622 (2000) · Zbl 0966.68156
[12] Biniaz, Ahmad; Bose, Prosenjit; Maheshwari, Anil; Smid, Michiel H. M., Plane bichromatic trees of low degree, Discrete Comput. Geom., 59, 4, 864-885 (2018) · Zbl 1395.05035
[13] Blagojevic, Pavle V. M.; Rote, Günter; Steinmeyer, Johanna K.; Ziegler, Günter M., Convex equipartitions of colored point sets, Discrete Comput. Geom., 61, 2, 355-363 (2019) · Zbl 1407.52031
[14] Brodén, Björn; Hammar, Mikael; Nilsson, Bengt J., Guarding lines and 2-link polygons is APX-hard, (Proc. 13th Canadian Conference on Computational Geometry. Proc. 13th Canadian Conference on Computational Geometry, CCCG (2001)), 45-48, URL http://www.cccg.ca/proceedings/2001/mikael-2351.ps.gz
[15] Devillers, Olivier; Hurtado, Ferran; Károlyi, Gyula; Seara, Carlos, Chromatic variants of the Erdős-Szekeres theorem on points in convex position, Comput. Geom., 26, 3, 193-208 (2003) · Zbl 1034.52014
[16] Dumitrescu, Adrian; Gerbner, Dániel; Keszegh, Balázs; Tóth, Csaba D., Covering paths for planar point sets, Discrete Comput. Geom., 51, 2, 462-484 (2014) · Zbl 1294.05102
[17] Dumitrescu, Adrian; Jiang, Minghui, On the approximability of covering points by lines and related problems, Comput. Geom., 48, 9, 703-717 (2015) · Zbl 1335.65029
[18] Dumitrescu, Adrian; Kaye, Rick, Matching colored points in the plane: Some new results, Comput. Geom., 19, 1, 69-85 (2001) · Zbl 0990.68170
[19] Fan, Chenglin; Luo, Jun; Wang, Wencheng; Zhong, Farong; Zhu, Binhai, On some proximity problems of colored sets, J. Comput. Sci. Tech., 29, 5, 879-886 (2014)
[20] Fleischer, Rudolf; Xu, Xiaoming, Computing minimum diameter color-spanning sets is hard, Inform. Process. Lett., 111, 21-22, 1054-1056 (2011) · Zbl 1260.68153
[21] Holmsen, Andreas F.; Kynčl, Jan; Valculescu, Claudiu, Near equipartitions of colored point sets, Comput. Geom., 65, 35-42 (2017) · Zbl 1377.65026
[22] Riko Jacob, Gerth Stølting Brodal, Dynamic planar convex hull, Manuscript, abs/1902.11169, 2019, arXiv:1902.11169. · Zbl 0966.68522
[23] Ju, Wenqi; Fan, Chenglin; Luo, Jun; Zhu, Binhai; Daescu, Ovidiu, On some geometric problems of color-spanning sets, J. Combin. Optim., 26, 2, 266-283 (2013) · Zbl 1275.90080
[24] Kaneko, Atsushi; Kano, Mikio, Discrete geometry on red and blue points in the plane: A survey, (Aronov, Boris; Basu, Saugata; Pach, János; Sharir, Micha, Discrete and Computational Geometry: The Goodman-Pollack Festschrift (2003), Springer: Springer Berlin), 551-570 · Zbl 1079.52505
[25] Kano, Mikio; Kynčl, Jan, The Hamburger theorem, Comput. Geom., 68, 167-173 (2018) · Zbl 1380.05068
[26] Kano, Mikio; Suzuki, Kazuhiro; Uno, Miyuki, Properly colored geometric matchings and 3-trees without crossings on multicolored points in the plane, (Akiyama, Jin; Ito, Hiro; Sakai, Toshinori, Discrete and Computational Geometry and Graphs. Discrete and Computational Geometry and Graphs, JCDCGG. Discrete and Computational Geometry and Graphs. Discrete and Computational Geometry and Graphs, JCDCGG, LNCS, vol. 8845 (2014), Springer), 96-111 · Zbl 1452.05064
[27] Kratsch, Stefan; Philip, Geevarghese; Ray, Saurabh, Point line cover: The easy kernel is essentially tight, ACM Trans. Algorithms, 12, 3, 40:1-40:16 (2016) · Zbl 1423.68547
[28] Kumar, V. S. Anil; Arya, Sunil; Ramesh, H., Hardness of set cover with intersection 1, (Montanari, Ugo; Rolim, José D. P.; Welzl, Emo, Proc. 27th International Colloquium on Automata, Languages and Programming. Proc. 27th International Colloquium on Automata, Languages and Programming, ICALP. Proc. 27th International Colloquium on Automata, Languages and Programming. Proc. 27th International Colloquium on Automata, Languages and Programming, ICALP, LNCS, vol. 1853 (2000), Springer), 624-635 · Zbl 0973.68080
[29] Kynčl, Jan; Pach, János; Tóth, Géza, Long alternating paths in bicolored point sets, Discrete Math., 308, 19, 4315-4321 (2008) · Zbl 1168.05320
[30] Matoušek, Jiří, (Geometric Discrepancy. Geometric Discrepancy, Algorithms and Combinatorics, vol. 18 (1999), Springer-Verlag: Springer-Verlag Berlin) · Zbl 0930.11060
[31] Matoušek, Jiří, (Using the Borsuk-Ulam Theorem. Using the Borsuk-Ulam Theorem, Universitext (2003), Springer-Verlag: Springer-Verlag Berlin) · Zbl 1016.05001
[32] Megiddo, Nimrod; Tamir, Arie, On the complexity of locating linear facilities in the plane, Oper. Res. Lett., 1, 5, 194-197 (1982) · Zbl 0507.90025
[33] Pruente, Jonas, Minimum diameter color-spanning sets revisited, Discrete Optim., 34 (2019) · Zbl 1506.90231
[34] Sakai, Toshinori, Balanced convex partitions of measures in \(\mathbb{R}^2\), Graphs Combin., 18, 1, 169-192 (2002) · Zbl 1002.52002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.