$C$ is a convex planar figure and $C_1,\dots,C_n$ are pairwise-disjoint convex subsets of $C$, like this:
A convex-preserving partition of $C$ is a partition $C=E_1\cup\dots\cup E_N$, , such that $N\geq n$, the $E_i$ are pairwise-disjoint convex figures, and for every $i=1,\dots,n$: $C_i\subseteq E_i$, i.e, each existing figure is contained in a unique new figure, like this:
For every $C,C_1,\dots,C_n$, let $F(C,C_1,\dots,C_n)$ be the smallest cardinality $N$ of a convex-preserving partition.
For every $n$, let $G(n)$ be the largest value of $F(C,C_1,\dots,C_n)$, for all combinations of $C,C_1,\dots,C_n$.
What is $G(n)$?
- Obviously $G(1)=1$.
- By the half-plane separation theorem, $G(2)=2$.
- By the above figure, $G(3)\geq 4$; there is apparently no convex-preserving partition with $N=3$.
What more can be said about $G(n)$?
Remark: I asked a similar question in cstheory.SE. There, $C$ and all its subsets were axis-parallel rectangles. In that case, I found an algorithm that proves $G(n)\leq 3n+1$.