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.
On rainbow quadrilaterals in colored point sets.(English)Zbl 07593903
Summary: Let \(S\) be a set of \(n\) points on the plane in general position whose elements have been colored with \(k\) colors. Arainbow 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 aconvex 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.
Cite
Full Text:DOI
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) |
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.
