On rainbow quadrilaterals in colored point sets. (English) Zbl 07593903

Arévalo, A.; Chávez-Jiménez, R.; Hernández-Mora, A.; López-López, R.; Marín, N.; Ramírez-Vigueras, A.; Solé-Pi, O.; Urrutia, J.

Graphs Comb. 38, No. 5, Paper No. 152, 16 p. (2022).

Summary: Let \(S\) be a set of \(n\) points on the plane in general position whose elements have been colored with \(k\) colors. A rainbow polygon of \(S\) is a polygon such that all of its vertices are elements of \(S\) and have different colors. In this paper we give \(O(k n^2)\)-time algorithms to solve the following problems: find a minimum(maximum)-area rainbow triangle, and a minimum(maximum)-area rainbow quadrilateral of \(S\), \(k \ge 3\). We also present an \(O(n^2)\)-time algorithm to determine if a 4-colored point set contains a convex rainbow quadrilateral, and an \(O(n^3)\)-time algorithm to determine if a 4-colored point set contains an empty rainbow quadrilateral, whether convex or not.

MSC:

68Uxx	Computing methodologies and applications
68Qxx	Theory of computing
52Axx	General convexity

Keywords:

colored point sets; rainbow polygons; minimum-area polygons; empty polygons

References:

[1]	Aichholzer, O.; Fabila-Monroy, R.; Flores-Penaloza, D.; Hackl, T.; Huemer, C.; Urrutia, J., Empty monochromatic triangles, Comput Geom, 42, 9, 934-938 (2009) · Zbl 1193.52008 · doi:10.1016/j.comgeo.2009.04.002
[2]	Aichholzer, O.; Fabila-Monroy, R.; Hackl, T.; Huemer, C.; Urrutia, J., Empty monochromatic simplices, Discrete Comput Geom, 51, 2, 362-393 (2014) · Zbl 1294.05194 · doi:10.1007/s00454-013-9565-2
[3]	Aichholzer, O., Urrutia, J., Vogtenhuber, B.: Balanced 6-holes in bichromatic point sets. In: Japanese Conference on Discrete and Computational Geometry, pp. 5-6. (2013)
[4]	Asano, T.; Asano, T.; Guibas, L.; Hershberger, J.; Imai, H., Visibility of disjoint polygons, Algorithmica, 1, 1-4, 49-63 (1986) · Zbl 0611.68062 · doi:10.1007/BF01840436
[5]	Bautista-Santiago, C.; Díaz-Báñez, JM; Lara, D.; Pérez-Lantero, P.; Urrutia, J.; Ventura, I., Computing optimal islands, Oper. Res. Lett., 39, 4, 246-251 (2011) · Zbl 1242.90183 · doi:10.1016/j.orl.2011.04.008
[6]	Bereg, S.; Díaz-Báñez, JM; Fabila-Monroy, R.; Pérez-Lantero, P.; Ramírez-Vigueras, A.; Sakai, T.; Urrutia, J.; Ventura, I., On balanced 4-holes in bichromatic point sets, Comput. Geom., 48, 3, 169-179 (2015) · Zbl 1307.52009 · doi:10.1016/j.comgeo.2014.09.004
[7]	Chan, TM, More logarithmic-factor speedups for 3sum,(median,+)-convolution, and some geometric 3sum-hard problems, ACM Trans. Algorithms (TALG), 16, 1, 1-23 (2019) · Zbl 1454.68210
[8]	Chandran, S.; Mount, DM, A parallel algorithm for enclosed and enclosing triangles, International Journal of Computational Geometry & Applications, 2, 2, 191-214 (1992) · Zbl 0762.68061 · doi:10.1142/S0218195992000123
[9]	Chazelle, B.; Guibas, LJ; Lee, DT, The power of geometric duality, BIT Numer. Math., 25, 1, 76-90 (1985) · Zbl 0603.68072 · doi:10.1007/BF01934990
[10]	Cravioto-Lagos, J.; González-Martínez, AC; Sakai, T.; Urrutia, J., On almost empty monochromatic triangles and convex quadrilaterals in colored point sets, Graphs Combin., 35, 6, 1475-1493 (2019) · Zbl 1431.05030 · doi:10.1007/s00373-019-02081-8
[11]	Devillers, O.; Hurtado, F.; Károlyi, G.; Seara, C., Chromatic variants of the erdos-szekeres theorem on points in convex position, Comput. Geom., 26, 3, 193-208 (2003) · Zbl 1034.52014 · doi:10.1016/S0925-7721(03)00013-0
[12]	Edelsbrunner, H.; Guibas, LJ, Topologically sweeping an arrangement, J. Comput. Syst. Sci., 38, 1, 165-194 (1989) · Zbl 0676.68013 · doi:10.1016/0022-0000(89)90038-X
[13]	Edelsbrunner, H.; O’Rourke, J.; Seidel, R., Constructing arrangements of lines and hyperplanes with applications, SIAM J. Comput., 15, 2, 341-363 (1986) · Zbl 0603.68104 · doi:10.1137/0215024
[14]	Eppstein, D.: New algorithms for minimum area k-gons. In: Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, pp. 83-88 (1992) · Zbl 0829.68117
[15]	Eppstein, D.; Overmars, M.; Rote, G.; Woeginger, G., Finding minimum area k-gons, Discrete & Computational Geometry, 7, 1, 45-58 (1992) · Zbl 0746.68038 · doi:10.1007/BF02187823
[16]	Erdös, P.; Szekeres, G., A combinatorial problem in geometry, Compos. Math., 2, 463-470 (1935) · JFM 61.0651.04
[17]	Fabila-Monroy, R.; Perz, D.; Trujillo-Negrete, AL, Empty rainbow triangles in k-colored point sets, Comput. Geom., 95 (2021) · Zbl 1516.68104 · doi:10.1016/j.comgeo.2020.101731
[18]	Flores-Peñaloza, D.; Kano, M.; Martínez-Sandoval, L.; Orden, D.; Tejel, J.; Tóth, CD; Urrutia, J.; Vogtenhuber, B., Rainbow polygons for colored point sets in the plane, Discret. Math., 344, 7 (2021) · Zbl 1466.52007 · doi:10.1016/j.disc.2021.112406
[19]	Gajentaan, A.; Overmars, MH, On a class of \({O}(n^2)\) problems in computational geometry, Comput. Geom., 5, 3, 165-185 (1995) · Zbl 0839.68105 · doi:10.1016/0925-7721(95)00022-2
[20]	Ghosh, SK, Visibility algorithms in the plane (2007), Cambridge: Cambridge University Press, Cambridge · Zbl 1149.68076 · doi:10.1017/CBO9780511543340
[21]	Hêche, JF; Liebling, TM, Finding minimum area simple pentagons, Oper. Res. Lett., 21, 5, 229-233 (1997) · Zbl 0908.90212 · doi:10.1016/S0167-6377(97)00051-5
[22]	van der Hoog, I., Keikha, V., Löffler, M., Mohades, A., Urhausen, J.: Maximum-area triangle in a convex polygon, revisited. Inf. Process. Lett. p. 105943 (2020) · Zbl 1441.68272
[23]	Jin, K.: Maximal area triangles in a convex polygon. arXiv:1707.04071 (2017)
[24]	Kallus, Y.: A linear-time algorithm for the maximum-area inscribed triangle in a convex polygon. arXiv:1706.03049 (2017)
[25]	Pach, J.; Tóth, G., Monochromatic empty triangles in two-colored point sets, Discret. Appl. Math., 161, 9, 1259-1261 (2013) · Zbl 1277.05071 · doi:10.1016/j.dam.2011.08.026
[26]	Rote, G.: The largest contained quadrilateral and the smallest enclosing parallelogram of a convex polygon. arXiv:1905.11203 (2019)