Talks and Poster Presentations (with Proceedings-Entry):
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),
- 2019-07-25; in: "IWOCA 2019: Combinatorial Algorithms",
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. .
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.  up to a multiplicative constant and answers another
of their open problems.
"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.