Maximum number of regions in partition induced by convex $k$-vertex polygons

Question

I have a set $\mathcal{P}$ of $n$ convex $k$-gons (convex $k$-vertex polygons) on the (Euclidean) plane. These define a partition of the plane, or rather the plane sans the pointer on the contour of any of the polygons, into contiguous regions, each defined by the subset of polygons covering it.

For a given $n$ and $k$, and over all sets $\mathcal{P}$ - what is the maximum size of the induced partition?

Note: The polygons are of finite size.

---

Example: Consider a set $\mathcal{P}$ of two squares, one being the same as the other but rotated by $\pi/4$:

So, $n = \left|\mathcal{P}\right|$ and $k = 4$. The induced partition of the plane has 9 regions - the 8 right-angle triangles, and the octagonal interior - plus the "outside", for 10 overall.

Answer 1

Consider two $k$-gons, $A$ and $B$. Since we are talking about convex polygons, each edge of $A$ can at most cut $B$ at two points, with one point entering the polygon and with the other exiting. Thus, we will have a total of $2k$ intersection points. Now consider the planar graph of the vertices of the two $k$-gons and these $2k$ intersection points. Originally, there were $k$ edges in each of the $k$-gons (total $2k$). Each new intersection point splits two of the participating edges into two parts, thus introducing two new edges. Thus, $|V| = k + k + 2k = 4k$ and $|E| = k + k + 2\times2k = 6k$.

Using Eular's formula, $|V| - |E| + |F| = 2$, we have $|F| = 6k - 4k + 2 = 2k + 2$. Since in your case $k = 4$, you have $2\times4 + 2 = 10$ faces. Here, we are assuming the two polygons maximally intersect each other to maximize the number of faces.

I hope you can now generalize this for $n$ number of $k$-gons.

Use recurrences:
$|V_{n+1}| = |V_{n}| + k + n\times 2k$ with $V_1 = k$
$|E_{n+1}| = |E_{n}| + $_____ with $E_1 = k$
Hence $|F_{n+1}| = |F_{n}| + $____ with $F_1 = 2$

PS: The counting idea is based on this video (made by 3Blue1Brown) on the maximum number of regions that can be formed in a circle by the number of chords of the circle.