Abstract
In 1935, Erdős and Szekeres proved that every set of n points in general position in the plane contains the vertices of a convex polygon of \(\frac{1}{2}\log _2(n)\) vertices. In 1961, they constructed, for every positive integer t, a set of \(n:=2^{t-2}\) points in general position in the plane, such that every convex polygon with vertices in this set has at most \(\log _2(n)+1\) vertices. In this paper we show how to realize their construction in an integer grid of size \(O(n^2 \log _2(n)^3).\)
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
More accurately, \(P_{r}\) contains a subset with the same order type as \(S_{k,l}.\)
References
Alon, N., Katchalski, M., Pulleyblank, W.R.: The maximum size of a convex polygon in a restricted set of points in the plane. Discret. Comput. Geom. 4(3), 245–251 (1989)
Barba, L., Duque, F., Fabila-Monroy, R., Hidalgo-Toscano, C.: Drawing the Horton set in an integer grid of minimum size. Comput. Geom. 63, 10–19 (2017)
Brass, P., Moser, W., Pach, J.: Research Problems in Discrete Geometry. Springer, New York (2005)
Chung, F.R.K., Graham, R.L.: Forced convex \(n\)-gons in the plane. Discret. Comput. Geom. 19(3), 367–371 (1998)
Erdős, P.: Some more problems on elementary geometry. Aust. Math. Soc. Gaz. 5(2), 52–54 (1978)
Erdős, P., Szekeres, G.: A combinatorial problem in geometry. Compos. Math. 2, 463–470 (1935)
Erdős, P., Szekeres, G.: On some extremum problems in elementary geometry. Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 3–4, 53–62 (1960/1961)
Gerken, T.: Empty convex hexagons in planar point sets. Discret. Comput. Geom. 39(1–3), 239–272 (2008)
Harborth, H.: Konvexe Fünfecke in ebenen Punktmengen. Elem. Math. 33(5), 116–118 (1978)
Horton, J.D.: Sets with no empty convex 7-gons. Can. Math. Bull. 26(4), 482–484 (1983)
Kalbfleisch, J.G., Stanton, R.G.: On the maximum number of coplanar points containing no convex \(n\)-gons. Util. Math. 47, 235–245 (1995)
Kleitman, D., Pachter, L.: Finding convex sets among points in the plane. Discret. Comput. Geom. 19(3), 405–410 (1998)
Matoušek, J.: Lectures on Discrete Geometry. Graduate Texts in Mathematics, vol. 212. Springer, New York (2002)
Mojarrad, H.N., Vlachos, G.: An improved upper bound for the Erdős–Szekeres conjecture. Discret. Comput. Geom. 56(1), 165–180 (2016)
Morris, W., Soltan, V.: The Erdős–Szekeres problem on points in convex position—a survey. Bull. Am. Math. Soc. (N.S.) 37(4), 437–458 (2000)
Nicolás, C.M.: The empty hexagon theorem. Discret. Comput. Geom. 38(2), 389–397 (2007)
Norin, S., Yuditsky, Y.: Erdős–Szekeres without induction. Discret. Comput. Geom. 55(4), 963–971 (2016)
Suk, A.: On the Erdős–Szekeres convex polygon problem. ar**v:1604.08657 (2016)
Tóth, G., Valtr, P.: Note on the Erdős–Szekeres theorem. Discret. Comput. Geom. 19(3), 457–459 (1998)
Tóth, G., Valtr, P.: The Erdős–Szekeres theorem: upper bounds and related results. In: Goodman, J.E., Pach, J., Welzl, E. (eds.) Combinatorial and Computational Geometry. Mathematical Sciences Research Institute Publications, vol. 52, pp. 557–568. Cambridge University Press, Cambridge (2005)
Valtr, P.: Convex independent sets and 7-holes in restricted planar point sets. Discret. Comput. Geom. 7(2), 135–152 (1992)
Valtr, P.: Planar point sets with bounded ratios of distances. PhD Thesis, Freie Universität Berlin (1994)
Vlachos, G.: On a conjecture of Erdős and Szekeres. ar**v:1505.07549 (2015)
Acknowledgements
The research was supported by Conacyt of Mexico Grant 253261.
Author information
Authors and Affiliations
Corresponding author
Additional information
Editor in Charge: János Pach
Rights and permissions
About this article
Cite this article
Duque, F., Fabila-Monroy, R. & Hidalgo-Toscano, C. Point Sets with Small Integer Coordinates and No Large Convex Polygons. Discrete Comput Geom 59, 461–476 (2018). https://doi.org/10.1007/s00454-017-9931-6
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-017-9931-6