On Erdős-Szekeres-type problems for \(k\)-convex point sets. (English) Zbl 1448.52013

Summary: We study Erdős-Szekeres-type problems for \(k\)-convex point sets, a recently introduced notion that naturally extends the concept of convex position. A finite set \(S\) of \(n\) points is \(k\)-convex if there exists a spanning simple polygonization of \(S\) such that the intersection of any straight line with its interior consists of at most \(k\) connected components. We address several open problems about \(k\)-convex point sets. In particular, we extend the well-known Erdős-Szekeres Theorem by showing that, for every fixed \(k \in \mathbb{N} \), every set of \(n\) points in the plane in general position (with no three collinear points) contains a \(k\)-convex subset of size at least \(\Omega (\log^k n)\). We also show that there are arbitrarily large 3-convex sets of \(n\) points in the plane in general position whose largest 1-convex subset has size \(O(\log n)\). This gives a solution to a problem posed by O. Aichholzer et al. [Comput. Geom. 47, No. 8, 809–832 (2014; Zbl 1292.52001)]. We prove that there is a constant \(c > 0\) such that, for every \(n \in \mathbb{N}\), there is a set \(S\) of \(n\) points in the plane in general position such that every 2-convex polygon spanned by at least \(c \cdot \log n\) points from \(S\) contains a point of \(S\) in its interior. This matches an earlier upper bound by Aichholzer et al. [loc. cit.] up to a multiplicative constant and answers another of their open problems.


52C10 Erdős problems and related topics of discrete geometry


Zbl 1292.52001
Full Text: DOI


[1] Aichholzer, Oswin; Aurenhammer, Franz; Demaine, Erik D.; Hurtado, Ferran; Ramos, Pedro; Urrutia, Jorge, On \(k\)-convex polygons, Comput. Geom., 45, 3, 73-87 (2012) · Zbl 1244.52005
[2] Aichholzer, Oswin; Aurenhammer, Franz; Hackl, Thomas; Hurtado, Ferran; Pilz, Alexander; Ramos, Pedro; Urrutia, Jorge; Valtr, Pavel; Vogtenhuber, Birgit, On \(k\)-convex point sets, Comput. Geom., 47, 8, 809-832 (2014) · Zbl 1292.52001
[3] Aichholzer, Oswin; Balko, Martin; Hackl, Thomas; Pilz, Alexander; Ramos, Pedro; Valtr, Pavel; Vogtenhuber, Birgit, Holes in 2-convex point sets, Comput. Geom., 74, 38-49 (2018) · Zbl 1432.52030
[4] Bárány, Imre; Valtr, Pavel, A positive fraction Erdős-Szekeres theorem, Discrete Comput. Geom., 19, 3, 335-342 (1998), (special issue) · Zbl 0914.52007
[5] Erdős, Paul, Some more problems on elementary geometry, Austral. Math. Soc. Gaz., 5, 2, 52-54 (1978) · Zbl 0417.52002
[6] Erdős, Paul; Szekeres, George, A combinatorial problem in geometry, Compos. Math., 2, 463-470 (1935) · Zbl 0012.27010
[7] Erdős, Paul; Szekeres, George, On some extremum problems in elementary geometry, Ann. Univ. Sci. Budapest. Eötvös Sect. Math., 3-4, 53-62 (1960) · Zbl 0103.15502
[8] Gerken, Tobias, Empty convex hexagons in planar point sets, Discrete Comput. Geom., 39, 1-3, 239-272 (2008) · Zbl 1184.52016
[9] Harborth, Heiko, Konvexe Fünfecke in ebenen Punktmengen, Elem. Math., 33, 5, 116-118 (1978) · Zbl 0397.52005
[10] Holmsen, Andreas F.; Mojarrad, Hossein Nassajian; Pach, János; Tardos, Gábor, Two extensions of the Erdős-Szekeres problem (2017), Preliminary version: http://arxiv.org/abs/1710.11415
[11] Horton, Joseph D., Sets with no empty convex \(7\)-gons, Canad. Math. Bull., 26, 4, 482-484 (1983) · Zbl 0521.52010
[12] Matoušek, Jiří, (Lectures on Discrete Geometry. Lectures on Discrete Geometry, Graduate Texts in Mathematics, vol. 212 (2002), Springer-Verlag: Springer-Verlag New York), xvi+481 · Zbl 0999.52006
[13] Nicolás, Carlos M., The empty hexagon theorem, Discrete Comput. Geom., 38, 2, 389-397 (2007) · Zbl 1146.52010
[14] Pór, Attila; Valtr, Pavel, The partitioned version of the Erdős-Szekeres theorem, Discrete Comput. Geom., 28, 4, 625-637 (2002) · Zbl 1019.52011
[15] Suk, Andrew, On the Erdős-Szekeres convex polygon problem, J. Amer. Math. Soc., 30, 4, 1047-1053 (2017) · Zbl 1370.52032
[16] Thomson, Brian S.; Bruckner, Judith B.; Bruckner, Andrew M., Elementary Real Analysis (2001), Prentice-Hall · Zbl 0872.26001
[17] Valtr, Pavel, Convex independent sets and \(7\)-holes in restricted planar point sets, Discrete Comput. Geom., 7, 2, 135-152 (1992) · Zbl 0748.52005
[18] Valtr, Pavel, Sets in \(\mathbf{R}^d\) with no large empty convex subsets, Discrete Math., 108, 1-3, 115-124 (1992) · Zbl 0766.52003
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.