4-Holes in Point Sets

O. Aichholzer, R. Fabila-Monroy, H. González-Aguilar, T. Hackl, M. Heredia, C. Huemer, J. Urrutia, and B. Vogtenhuber

Abstract:

We consider a variant of a question of Erdos on the number of empty $k$-gons ($k$-holes) in a set of $n$ points in the plane, where we allow the $k$-gons to be non-convex. We show bounds and structural results on maximizing and minimizing the number of general 4-holes, and maximizing the number of non-convex 4-holes.

Reference: O. Aichholzer, R. Fabila-Monroy, H. González-Aguilar, T. Hackl, M. Heredia, C. Huemer, J. Urrutia, and B. Vogtenhuber. 4-Holes in point sets. In Proc. $27^{th}$ European Workshop on Computational Geometry EuroCG '11, pages 115-118, Morschach, Switzerland, 2011.