A finite set S of points in the plane in general position is k-convex if some spanning simple polygonization of S has the property that every straight line intersects its interior in at most k connected components; 1-convex is exactly convex position. Two Erdős–Szekeres-type extremal functions govern how large a k-convex substructure an arbitrary n-point set must contain: g(k,n) is the largest integer m such that every n-point set in general position contains a k-convex subset of size m, and f(k,j,n) is the largest integer m such that every k-convex n-point set contains a j-convex subset of size m. The classical theorem gives g(1,n) = Theta(log n); Aichholzer et al. (2014) proved g(2,n) = Theta(log^2 n), and Balko, Bhore, Martínez-Sandoval, and Valtr (2020) proved g(k,n) >= Omega(log^k n) for every fixed k, settling f(k,1,n) = Theta(log n) and f(k,2,n) = Theta(log^2 n) for k >= 3 along the way. No matching upper bounds are known for k >= 3: the correct asymptotic order of g(k,n) remains undetermined (only a weak O(k*sqrt(n)) upper bound is observed), and no asymptotic characterization of f(k,j,n) exists in its nontrivial range 3 <= j < k (for j >= k the value f(k,j,n) = n is immediate from the definition, since a polygonization meeting every line in at most k connected components also meets it in at most j components, so every k-convex set is then itself j-convex). The problem asks to determine these extremal functions: to find matching upper bounds for g(k,n) for fixed k >= 3, and to determine f(k,j,n) asymptotically for fixed k >= 3 and j >= 3, the second part of an open problem posed by Aichholzer et al.

Background

The classical Erdős–Szekeres theorem (1935) states that every sufficiently large set of points in the plane in general position (no three points collinear) contains a prescribed number of points in convex position, i.e. points forming the vertex set of a convex polygon; in quantitative form, every n-point set in general position contains a convex subset of size Theta(log n), and this is tight. Horton (1983) constructed arbitrarily large point sets containing no empty convex 7-gon (7 points in convex position with no other point of the set inside), showing that emptiness cannot be forced beyond hexagons.

Aichholzer, Aurenhammer, Demaine, Hurtado, Ramos, and Urrutia (2012) introduced k-convexity for simple polygons: a polygon is k-convex if every straight line intersects its interior in at most k connected components, so 1-convex polygons are exactly the convex polygons. They characterized 2-convex polygons and proved an Erdős–Szekeres-type result for them: every 2-convex polygon with n vertices contains a subset of at least ceil(sqrt(n/2)) vertices in convex position, which is tight. Aichholzer, Aurenhammer, Hackl, Hurtado, Pilz, Ramos, Urrutia, Valtr, and Vogtenhuber (2014) extended the notion to finite point sets: a point set S is k-convex if it admits a k-convex polygonization, that is, a simple polygon whose vertex set is exactly S and whose interior is intersected by every line in at most k connected components. Among other results they proved that every n-point set in general position is O(sqrt(n))-convex (with matching Omega(sqrt(n)) worst-case examples) and that every n-point set contains a 2-convex subset of size Theta(log^2 n). They posed a series of open problems, including: determine the function f(k,j,n) equal to the largest m such that every k-convex set of n points contains a j-convex subset of size m (with f(k,n) denoting the case j = 1), and determine the largest guaranteed k-convex subset of an arbitrary n-point set, the function now denoted g(k,n).

Balko, Bhore, Martínez-Sandoval, and Valtr (2020) resolved several of these problems. Their main theorem gives, for every fixed k, a constant C_k > 0 with g(k,n) >= C_k*(log n)^k for all large n, proved by induction on k using the positive-fraction Erdős–Szekeres theorem of Bárány and Valtr (a strengthening of the classical theorem guaranteeing that every sufficiently large point set in general position contains pairwise disjoint convex k-gons covering a positive constant fraction of the points); in the other direction they introduced combinatorial Devil's staircases, explicitly defined recursive 3-convex point sets of size 2^t whose largest 1-convex (convex-position) subset has size only O(t), showing f(k,1,n) = Theta(log n) for all k >= 3 and (together with the earlier Omega(log^2 n) guarantee for 2-convex subsets) f(k,2,n) = Theta(log^2 n) for all k >= 3. They also proved that the largest guaranteed empty 2-convex polygon in an n-point set has size Theta(log n), and gave explicit constructions showing that the classical bound, according to which the union of a k-convex set and an l-convex set is (k+l+1)-convex (improved to k+l when the two polygonizations intersect), is tight up to an additive constant.

Problem Statement

Determine the Erdős–Szekeres-type extremal functions for k-convex point sets that the 2020 results leave open, for fixed integers k >= 3 (and, for the second item, in the nontrivial range 3 <= j < k):

(1) The guaranteed size of a k-convex subset of an arbitrary point set. Let g(k,n) be the largest integer m such that every set of n points in the plane in general position contains a k-convex subset of size m, where a point set is k-convex if it admits a spanning simple polygonization whose interior is intersected by every straight line in at most k connected components. Known: g(1,n) = Theta(log n), g(2,n) = Theta(log^2 n), and g(k,n) = Omega(log^k n) for every fixed k (Balko et al. 2020). Determine the correct asymptotic order of g(k,n) as n -> infinity for fixed k >= 3; in particular, decide whether the Omega(log^k n) lower bound is tight, and if not, improve either bound.

(2) The guaranteed size of a j-convex subset of a k-convex point set (the second part of the subset-guarantee problem posed by Aichholzer et al. 2014). Let f(k,j,n) be the largest integer m such that every k-convex set of n points in general position contains a j-convex subset of size m. Known: f(k,1,n) = Theta(log n) and f(k,2,n) = Theta(log^2 n) for all k >= 3, f(2,1,n) = Theta(sqrt(n)), and f(k,j,n) = n whenever j >= k; this last value is immediate from the definitions, since a polygonization whose interior meets every line in at most k connected components also meets it in at most j components for any j >= k, so every k-convex set is itself a j-convex subset of full size. The open problem is the remaining range: determine f(k,j,n) asymptotically, upper and lower bounds, for fixed k >= 4 and 3 <= j <= k-1; in particular, decide for which such (k,j) the growth is polylogarithmic in n and whether the pattern f(k,j,n) = Theta(log^j n) continues past j = 2.

References

  1. Martin Balko, Sujoy Bhore, Leonardo Martínez-Sandoval, Pavel Valtr. On Erdős–Szekeres-type problems for k-convex point sets. European Journal of Combinatorics 89 (2020) 103157. DOI: 10.1016/j.ejc.2020.103157. https://doi.org/10.1016/j.ejc.2020.103157 (also in preliminary form in Proc. IWOCA 2019, LNCS 11638, pp. 35–47, DOI: 10.1007/978-3-030-25005-8_4)
  2. Oswin Aichholzer, Franz Aurenhammer, Thomas Hackl, Ferran Hurtado, Alexander Pilz, Pedro Ramos, Jorge Urrutia, Pavel Valtr, Birgit Vogtenhuber. On k-convex point sets. Computational Geometry 47 (8) (2014) 809–832. DOI: 10.1016/j.comgeo.2014.04.004. https://doi.org/10.1016/j.comgeo.2014.04.004
  3. Oswin Aichholzer, Franz Aurenhammer, Erik D. Demaine, Ferran Hurtado, Pedro Ramos, Jorge Urrutia. On k-convex polygons. Computational Geometry 45 (3) (2012) 73–87. DOI: 10.1016/j.comgeo.2011.09.001. https://doi.org/10.1016/j.comgeo.2011.09.001 (arXiv:1007.3607)
  4. Oswin Aichholzer, Martin Balko, Thomas Hackl, Alexander Pilz, Pedro Ramos, Pavel Valtr, Birgit Vogtenhuber. Holes in 2-convex point sets. Computational Geometry 74 (2018) 38–49. DOI: 10.1016/j.comgeo.2018.06.002. https://doi.org/10.1016/j.comgeo.2018.06.002
  5. Paul Erdős, George Szekeres. A combinatorial problem in geometry. Compositio Mathematica 2 (1935) 463–470. https://www.numdam.org/item/CM_1935__2__463_0/
  6. J. D. Horton. Sets with no empty convex 7-gons. Canadian Mathematical Bulletin 26 (4) (1983) 482–484. DOI: 10.4153/cmb-1983-077-8. https://doi.org/10.4153/cmb-1983-077-8
  7. Heather S. Blake, Stefan Felsner, Rimma Hämäläinen, Marcin Witkowski. On the Erdős-Szekeres Problem for Convex Permutations and Orthogonally Convex Point Sets. The Electronic Journal of Combinatorics 32 (4) (2025) #P4.49. DOI: 10.37236/13543. https://doi.org/10.37236/13543