Empty rainbow triangles in \(k\)-colored point sets.(English)Zbl 1516.68104
Summary: Let \(S\) be a set of \(n\) points in general position in the plane. Suppose that each point of \(S\) has been assigned one of \(k \geq 3\) possible colors and that there is the same number, \(m\), of points of each color class. This means \(n = k m\). A polygon with vertices on \(S\) is empty if it does not contain points of \(S\) in its interior; and it is rainbow if all its vertices have different colors. Let \(f(k, m)\) be the minimum number of empty rainbow triangles determined by \(S\). In this paper we give tight asymptotic bounds for this function. Furthermore, we show that \(S\) may not determine an empty rainbow quadrilateral for some arbitrarily large values of \(k\) and \(m\).
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
| 52C10 | Erdős problems and related topics of discrete geometry |
Cite
References:
| [1] | Aichholzer, O.; Balko, M.; Hackl, T.; Kyncl, J.; Parada, I.; Scheucher, M.; Valtr, P.; Vogtenhuber, B., A superlinear lower bound on the number of 5-holes, (33rd International Symposium on Computational Geometry (SoCG 2017) (2017), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik) ·Zbl 1432.52027 |
| [2] | Aichholzer, O.; Fabila-Monroy, R.; Flores-Peñaloza, D.; Hackl, T.; Huemer, C.; Urrutia, J., Empty monochromatic triangles, Comput. Geom., 42, 9, 934-938 (2009) ·Zbl 1193.52008 |
| [3] | Aichholzer, O.; Fabila-Monroy, R.; Hackl, T.; Huemer, C.; Pilz, A.; Vogtenhuber, B., Lower bounds for the number of small convex k-holes, Comput. Geom., 47, 5, 605-613 (2014) ·Zbl 1287.65011 |
| [4] | Aichholzer, O.; Hackl, T.; Huemer, C.; Hurtado, F.; Vogtenhuber, B., Large bichromatic point sets admit empty monochromatic 4-gons, SIAM J. Discrete Math., 23, 4, 2147-2155 (2010) ·Zbl 1204.52017 |
| [5] | Aichholzer, O.; Urrutia, J.; Vogtenhuber, B., Balanced 6-holes in linearly separable bichromatic point sets, Electron. Notes Discrete Math., 44, 181-186 (2013) |
| [6] | Bárány, I.; Füredi, Z., Empty simplices in Euclidean space, Can. Math. Bull., 30, 12 (1987) ·Zbl 0639.52006 |
| [7] | Bárány, I.; Valtr, P., Planar point sets with a small number of empty convex polygons, Studia Sci. Math. Hung., 41, 2, 243-266 (2004) ·Zbl 1075.52008 |
| [8] | Basu, D.; Basu, K.; Bhattacharya, B. B.; Das, S., Almost empty monochromatic triangles in planar point sets, Discrete Appl. Math., 210, 207-213 (2016) ·Zbl 1339.05040 |
| [9] | Bereg, S.; Díaz-Báñez, J. M.; 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 |
| [10] | Brass, P., Empty monochromatic fourgons in two-colored point sets, Geombinatorics, 14, 2, 5-7 (2004) ·Zbl 1062.52016 |
| [11] | Dehnhardt, K., Leere konvexe Vielecke in ebenen Punktmengen (1987), TU: TU Braunschweig, PhD thesis ·Zbl 0629.52016 |
| [12] | Devillers, O.; Hurtado, F.; Károlyi, G.; Seara, C., Chromatic variants of the Erdős-Szekeres theorem on points in convex position, Comput. Geom., 26, 3, 193-208 (2003) ·Zbl 1034.52014 |
| [13] | Dumitrescu, A., Planar sets with few empty convex polygons, Studia Sci. Math. Hung., 36, 1-2, 93-109 (2000) ·Zbl 0980.52007 |
| [14] | Erdős, P., Some more problems on elementary geometry, Aust. Math. Soc. Gaz., 5, 2, 52-54 (1978) ·Zbl 0417.52002 |
| [15] | Erdős, P.; Szekeres, G., A combinatorial problem in geometry, Compos. Math., 2, 463-470 (1935) ·JFM 61.0651.04 |
| [16] | Friedman, E., 30 two-colored points with no empty monochromatic convex fourgons, Geombinatorics, 14, 2, 53-54 (2004) ·Zbl 1063.52011 |
| [17] | García, A., A Note on the Number of Empty Triangles, 249-257 (2012), Springer ·Zbl 1374.68663 |
| [18] | Gerken, T., Empty convex hexagons in planar point sets, Discrete Comput. Geom., 39, 1-3, 239-272 (2008) ·Zbl 1184.52016 |
| [19] | Harborth, H., Konvexe Fünfecke in ebenen Punktmengen, Elem. Math., 33, 5, 116-118 (1978) ·Zbl 0397.52005 |
| [20] | Horton, J. D., Sets with no empty convex 7-gons, Can. Math. Bull., 26, 4, 482-484 (1983) ·Zbl 0521.52010 |
| [21] | Huemer, C.; Seara, C., 36 two-colored points with no empty monochromatic convex fourgons, Geombinatorics, 19, 1, 5-6 (2009) ·Zbl 1506.05066 |
| [22] | Katchalski, M.; Meir, A., On empty triangles determined by points in the plane, Acta Math. Hung., 51, 3-4, 323-328 (1988) ·Zbl 0655.52007 |
| [23] | Koshelev, V., On Erdős-Szekeres problem and related problems (2009), arXiv preprint ·Zbl 1273.52021 |
| [24] | Liu, L.; Zhang, Y., Almost empty monochromatic quadrilaterals in planar point sets, Math. Notes, 103, 3-4, 415-429 (2018) ·Zbl 1395.52003 |
| [25] | Nicolás, C. M., The empty hexagon theorem, Discrete Comput. Geom., 38, 2, 389-397 (2007) ·Zbl 1146.52010 |
| [26] | Pach, J.; Tóth, G., Monochromatic empty triangles in two-colored point sets, Discrete Appl. Math., 161, 9, 1259-1261 (2013) ·Zbl 1277.05071 |
| [27] | Valtr, P., Convex independent sets and 7-holes in restricted planar point sets, Discrete Comput. Geom., 7, 135-152 (1992) ·Zbl 0748.52005 |
| [28] | Valtr, P., On the minimum number of empty polygons in planar point sets, Studia Sci. Math. Hung., 30, 1-2, 155-163 (1995) ·Zbl 0867.52004 |
| [29] | van Gulik, R., 32 two-colored points with no empty monochromatic convex fourgons, Geombinatorics, 15, 1, 32-33 (2005) |
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.
