We consider a variant of a question of Erd?s on the number of empty κ-gons (κ-holes) in a set of n points in the plane, where we allow the κ-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. In particular, we show that for n ≥ 9, the maximum number of general 4-holes is (_4~n); the minimum number of general 4-holes is at least 5/2n~2 - Θ(n); and the maximum number of non-convex 4-holes is at least 1/2n~3 - Θ(n~2logn) and at most 1/2n~3 - Θ(n~2).
展开▼
