@inproceedings{d973006f2a9a484fbdb9f3d3e5ec126b,

title = "Holes in 2-convex point sets",

abstract = "Let S be a set of n points in the plane in general position (no three points from S are collinear). For a positive integer k, a k-hole in S is a convex polygon with k vertices from S and no points of S in its interior. For a positive integer l, a simple polygon P is l-convex if no straight line intersects the interior of P in more than l connected components. A point set S is l-convex if there exists an l-convex polygonization of S. Considering a typical Erd{\H o}s-Szekeres-type problem, we show that every 2-convex point set of size n contains an Ω(log n)-hole. In comparison, it is well known that there exist arbitrarily large point sets in general position with no 7-hole. Further, we show that our bound is tight by constructing 2-convex point sets with holes of size at most O(log n).",

keywords = "2-convex set, Convex position, Hole, Horton set, Point set",

author = "Oswin Aichholzer and Martin Balko and Thomas Hackl and Alexander Pilz and Pedro Ramos and Pavel Valtr and Birgit Vogtenhuber",

year = "2018",

month = jan,

day = "1",

doi = "10.1007/978-3-319-78825-8_14",

language = "English",

isbn = "9783319788241",

volume = "10765",

series = "Lecture Notes in Computer Science ",

publisher = "Springer Verlag Heidelberg",

pages = "169--181",

booktitle = "Combinatorial Algorithms - 28th International Workshop, IWOCA 2017, Revised Selected Papers",

note = "28th International Workshop on Combinational Algorithms, IWOCA 2017 ; Conference date: 17-07-2017 Through 21-07-2017",

}