If $S$ is set of $n$ points in the plane, then $S$ has $2^n$ different subsets. We say that a subset $T\subseteq S$ is "defined by a polygon" if there is a polygon which has $T$ in its interior and $S\setminus T$ in its exterior.
For every $n$, define $F(n)$ as the maximum number of subsets defined by a polygon (maximum over all subsets of $n$ points).
What is an asymptotic bound on $F(n)$ when the defining polygon is:
- A square?
- A rectangle?
- A convex polygon with $d$ sides?
- Any convex polygon?
Is there a general reference for solving such problems?