×

On balanced 4-holes in bichromatic point sets. (English) Zbl 1307.52009

Summary: Let \(S=R\cup B\) be a point set in the plane in general position such that each of its elements is colored either red or blue, where \(R\) and \(B\) denote the points colored red and the points colored blue, respectively. A quadrilateral with vertices in \(S\) is called a 4-hole if its interior is empty of elements of \(S\). We say that a 4-hole of \(S\) is balanced if it has 2 red and 2 blue points of \(S\) as vertices.
In this paper, we prove that if \(R\) and \(B\) contain \(n\) points each then \(S\) has at least \(\frac{n^2-4n}{12}\) balanced 4-holes, and this bound is tight up to a constant factor. Since there are two-colored point sets with no balanced convex 4-holes, we further provide a characterization of the two-colored point sets having this type of 4-holes.

MSC:

52C10 Erdős problems and related topics of discrete geometry
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] 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 (January 2010) · Zbl 1204.52017
[2] Aichholzer, O.; Fabila-Monroy, R.; González-Aguilar, H.; Hackl, T.; Heredia, M. A.; Huemer, C.; Urrutia, J.; Vogtenhuber, B., 4-holes in point sets, (27th European Workshop on Computational Geometry EuroCG’11. 27th European Workshop on Computational Geometry EuroCG’11, Morschach, Switzerland (2011)), 115-118
[3] Aichholzer, O.; Urrutia, J.; Vogtenhuber, B., Balanced 6-holes in linearly separable bichromatic point sets, Electron. Notes Discrete Math., 44, 0, 181-186 (2013)
[4] Devillers, O.; Hurtado, F.; Károlyi, G.; Seara, C., Chromatic variants of the Erdős-Szekeres theorem on points in convex position, Comput. Geom. Theory Appl., 26, 3, 193-208 (November 2003) · Zbl 1034.52014
[5] Erdős, P., Some more problems on elementary geometry, Aust. Math. Soc. Gaz., 5, 52-54 (1978) · Zbl 0417.52002
[6] Erdős, P.; Szekeres, G., A combinatorial problem in geometry, Compos. Math., 2, 463-470 (1935) · JFM 61.0651.04
[7] García, A.; Noy, M.; Tejel, J., Lower bounds on the number of crossing-free subgraphs of \(k_n\), Comput. Geom. Theory Appl., 16, 4, 211-221 (2000) · Zbl 0966.68158
[8] Gerken, T., Empty convex hexagons in planar point sets, Discrete Comput. Geom., 39, 1, 239-272 (March 2008) · Zbl 1184.52016
[9] Harborth, H., Konvexe fünfecke in ebenen punktmengen, Elem. Math., 33, 116-118 (1978) · Zbl 0397.52005
[10] Horton, J. D., Sets with no empty convex 7-gons, Can. Math. Bull., 26, 482-484 (1983) · Zbl 0521.52010
[11] Huemer, C.; Seara, C., 36 two-colored points with no empty monochromatic convex fourgons, Geombinatorics, XIX, 1, 5-6 (2009) · Zbl 1506.05066
[13] Mitchell, J. S.B.; Rote, G.; Sundaram, G.; Woeginger, G. J., Counting convex polygons in planar point sets, Inf. Process. Lett., 56, 1, 45-49 (1995) · Zbl 0875.68899
[14] Nicolas, C. M., The empty hexagon theorem, Discrete Comput. Geom., 38, 2, 389-397 (September 2007) · Zbl 1146.52010
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.