Abstract
For positive integers c, s ≥ 1, r ≥ 3, let W r (c, s) be the least integer such that if a set of at least W r (c, s) points in the plane, no three of which are collinear, is colored with c colors, then this set contains a monochromatic r-gon with at most s interior points. As is known, if r = 3, then W r (c, s)=W r (c, s). In this paper, we extend these results to the case r = 4. We prove that W4(2, 1) = 11, W4(3, 2) ≤ 120, and the least integer μ4(c) such that W4(c, μ4(c)) < ∞ is bounded by \(\left\lfloor {\frac{{c - 1}}{2}} \right\rfloor \cdot 2 \leqslant \mu 4\left( c \right) \leqslant 2c - 3\),where c ≥ 2.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
O. Aichholzer, F. Aurenhammer, P. Gonzalez-Nava, T. Hackl, C. Huemer, F. Hurtado, H. Krasser, S. Ray, and B. Vogtenhuber, “Matching edges and faces in polygonal partitions,” Comput. Geom. 39 (2), 134–141 (2008).
O. Aichholzer, T. Hackl, C. Huemer, F. Hurtado, and B. Vogtenhuber, “Large bichromatic point sets admit empty monochromatic 4-gons,” SIAMJ. DiscreteMath. 23 (4), 2147–2155 (2010).
D. Basu, K. Basu, B. B. Bhattacharya, and S. Das, “Almost empty monochromatic triangles in planar point sets,” Discrete Appl.Math. 210, 207–213 (2016).
P. Bose and G. Toussaint, “Characterizing and efficiently computing quadrangulations of planar point sets,” Comput. Aided Geom. Design 14 (8), 763–785 (1997).
P. Bose and G. Toussaint, “No quadrangulation is extremely odd,” Lecture Notes in Comput. Sci. 1004, 372–381 (1995).
O. Devillers, F. Hurtado, G. Károlyi, and C. Seara, “Chromatic variants of the Erdős-Szekeres theorem on points in convex position,” Comput. Geom. 26 (3), 193–208 (2003).
P. Erdős, “Some more problems on elementary geometry,” Austral.Math. Soc. Gaz. 5 (2), 52–54 (1978).
P. Erdős and G. Szekeres, “A combinatorial problem in geometry,” CompositoMath. 2, 464–470 (1935).
P. Erdős and G. Szekeres, “On some extremumproblems in elementary geometry,” Ann.Univ. Sci.Budapest, 3–4 (1960).
T. Gerken, “Empty convex hexagons in planar point sets,” Discrete Comput. Geom. 39 (1), 239–272 (2008).
C. Grima, C. Hernando, C. Huemer, and F. Hurtado, “On some partitioning problems for two-colored point sets,” in Proc. XIII Encuentros de Geometría Computacional Geometry, Zaragoza, Spain, 2009.
H. Harborth, “Konvexe Fünfecke in ebenen Punktmengen,” Elem.Math. 33, 116–118 (1978).
J. D. Horton, “Sets with no empty convex 7-gons,” Can. Math. Bull. 26 (4), 482–484 (1983).
V. A. Koshelev, “On the Erdős-Szekeres problem,” DokladyMathematics 76 (1), 603–605 (2007).
C.M. Nicolas, “The empty hexagon theorem,” Discrete Comput. Geom. 38 (2), 389–397 (2007).
H. Nyklová, “Almost empty polygons,” Studia Sci.Math. Hungar. 40(3), 269–286 (2003).
R. G. Stanton, “A combinatorial problem on convex regions,” in Proc. Louisiana Conf. Combinatorics, Graph Theory and Computing, Louisiana State Univ., Baton Rouge, La., Congr. Numer. 1, 180–188 (1970).
G. Szekeres and L. Peters, “Computer solution to the 17-point Erdős-Szekeres problem,” Anziam J. 48 (2), 151–164 (2006).
G. Tóth and P. Valtr, The Erdős–Szekeres theorem: Upper Bounds and Related Results, Charles Univ., 2004.
G. Toussaint, “Quadrangulations of planar sets,” in Proc. 4th International Workshop on Algorithms and Data Structures (WADS), Lecture Notes in Computer Science (Springer, New York, 1995), Vol. 955, pp. 218–227.
P. Valtr, “Convex independent sets and 7-holes in restricted planar point sets,” Discrete Comput.Geom. 7(1), 135–152 (1992).
P. Brass, W. Moser, and J. Pach, Research Problems in Discrete Geometry (Springer Science & Business Media, 2006).
J. Pach and P. K. Agarwal, Combinatorial Geometry (JohnWiley & Sons, 2011).
Author information
Authors and Affiliations
Corresponding author
Additional information
The article was submitted by the authors for the English version of the journal.
Rights and permissions
About this article
Cite this article
Liu, L., Zhang, Y. Almost Empty Monochromatic Quadrilaterals in Planar Point Sets. Math Notes 103, 415–429 (2018). https://doi.org/10.1134/S0001434618030082
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S0001434618030082