M. Balko, S. Bhore, L. Martinez-Sandoval, P. Valtr:

"On Erdős-Szekeres-type problems for k-convex point sets";

European Journal of Combinatorics,89(2020), 1 - 22.

We study Erdős-Szekeres-type problems fork-convex point sets,a recently introduced notion that naturally extends the conceptof convex position. A finite setSofnpoints isk-convexifthere exists a spanning simple polygonization ofSsuch that theintersection of any straight line with its interior consists of atmostkconnected components.We address several open problems aboutk-convex pointsets. In particular, we extend the well-known Erdős-SzekeresTheorem by showing that, for every fixedk∈N, every set ofnpoints in the plane ingeneral position(with no three collinearpoints) contains ak-convex subset of size at leastΩ(logkn).We also show that there are arbitrarily large 3-convex sets ofnpoints in the plane in general position whose largest 1-convexsubset has sizeO(logn). This gives a solution to a problem posedby Aichholzer et al. (2014).We prove that there is a constantc>0 such that, for everyn∈N, there is a setSofnpoints in the plane in general position such that every 2-convex polygon spanned by at leastc·lognpoints fromScontains a point ofSin its interior. Thismatches an earlier upper bound by Aichholzer et al. (2014) upto a multiplicative constant and answers another of their openproblems.

http://dx.doi.org/10.1016/j.ejc.2020.103157

https://publik.tuwien.ac.at/files/publik_293825.pdf

Created from the Publication Database of the Vienna University of Technology.