Publications in Scientific Journals:
M. Balko, S. Bhore, L. Martinez-Sandoval, P. Valtr:
"On Erdős-Szekeres-type problems for k-convex point sets";
European Journal of Combinatorics,
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.
"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
Electronic version of the publication:
Created from the Publication Database of the Vienna University of Technology.