On k-gons and k-holes in point sets
Conference Paper
Overview
Research
Additional Document Info
View All
Overview
abstract
We consider a variation of the classical Erd}os-Szekeres problems on the existence and number of convex k-gons and k-holes (empty k-gons) in a set of n points in the plane. Allowing the k-gons to be non-convex, we show bounds and structural results on maximizing and mini- mizing their numbers. Most noteworthy, for any k and sufficiently large n, we give a quadratic lower bound for the number of k-holes, and show that this number is maximized by sets in convex position. We also pro- vide an improved lower bound for the number of convex 6-holes.