Holes in two convex point sets

O. Aichholzer, M. Balko, T. Hackl, A. Pilz, P. Ramos, B. Vogtenhuber, and P. Valtr

Abstract:

Let $S$ be a finite set of $n$ points in the plane in general position. A $k-hole$ of $S$ is a simple polygon with $k$ vertices from $S$ and no points of $S$ in its interior. A simple polygon $P$ is $l$-convex if no straight line intersects the interior of $P$ in more than $l$ connected components. Moreover, a point set $S$ is $l$-convex if there exists an $l$-convex polygonalization of $S$. Considering a typical Erdos-Szekeres type problem we show that every 2-convex point set of size $n$ contains a convex hole of size $\Omega(log n)$. This is in contrast to the well known fact that there exist general point sets of arbitrary size that do not contain a convex 7-hole. Further, we show that our bound is tight by providing a construction for 2-convex point sets with holes of size at most $O(log n)$.

Reference: O. Aichholzer, M. Balko, T. Hackl, A. Pilz, P. Ramos, B. Vogtenhuber, and P. Valtr. Holes in two convex point sets. In Proc. $32^{st}$ European Workshop on Computational Geometry EuroCG '16, pages 263-266, Lugano, Switzerland, 2016.