[Back]

M. Balko, S. Bhore, L. Martinez-Sandoval, P. Valtr:
"On Erdös-Szekeres-Type Problems for k-convex Point Sets";
Talk: International Workshop on Combinatorial Algorithms (IWOCA), Pisa; 2019-07-23 - 2019-07-25; in: "IWOCA 2019: Combinatorial Algorithms", LNCS, 11638 (2019), ISBN: 978-3-030-25004-1; 35 - 47.

We study Erd˝os-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˝os-Szekeres Theorem by showing that,
for every fixed k ∈ 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 Ω(logk 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
Aichholzer et al. [2].
We prove that there is a constant c > 0 such that, for every n ∈ 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 · log n points from S contains
a point of S in its interior. This matches an earlier upper bound by
Aichholzer et al. [2] up to a multiplicative constant and answers another
of their open problems.

http://dx.doi.org/10.1007/978-3-030-25005-8_4

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