On Erdős-Szekeres-type problems for 𝑘-convex point sets

Abstract

We study Erdős-Szekeres-type problems for 𝑘-convex point sets,a recently introduced notion that naturally extends the concept of convex position. A finite set 𝑆 of 𝑛 points is 𝑘-convex if there exists a spanning simple polygonization of 𝑆 such that the intersection of any straight line with its interior consists of at most 𝑘 connected components. We address several open problems about 𝑘-convex pointsets. In particular, we extend the well-known Erdős-Szekeres Theorem by showing that, for every fixed 𝑘∈ℕ, every set ofnpoints in the plane ingeneral position(with no three collinearpoints) contains a 𝑘-convex subset of size at least Ω(logk𝑛).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𝑛). This gives a solution to a problem posed by Aichholzer et al. (2014).We prove that there is a constant c>0 such that, for every 𝑛∈ℕ, 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·log 𝑛 points from S contains a point of S in its interior. This matches an earlier upper bound by Aichholzer et al. (2014) up to a multiplicative constant and answers another of their open problems.