[Zurück]


Zeitschriftenartikel:

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), S. 1 - 22.



Kurzfassung englisch:
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.


"Offizielle" elektronische Version der Publikation (entsprechend ihrem Digital Object Identifier - DOI)
http://dx.doi.org/10.1016/j.ejc.2020.103157

Elektronische Version der Publikation:
https://publik.tuwien.ac.at/files/publik_293825.pdf


Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.