Partitioning a union of convex shapes

Question

A union of two axes-parallel rectangles can always be partitioned into at most $3$ pairwise-disjoint axes-parallel rectangles:

Is there an analogous lemma for convex figures? I.e, is there a number $k$ such that a union of two convex figures can always be partitioned into at most $k$ pairwise-disjoint convex figures?

Answer 1

As Michael Burr mentions in a comment, this is not bounded with unrestricted convex figures, because we can take two regular $n$-gons rotated at an offset from one another:

I thought I would illustrate a proof that this takes at least $n+1$ convex pieces, since it was not originally clear to me how to rigorously show that the number of pieces in such a construction is unbounded. ($n+1$ is the best possible, by taking one of the original polygons and the $n$ leftover triangles.)

Consider which of the $2n$ "outer" vertices lie in the same convex piece. Clearly, no two such vertices which are adjacent can lie in the same convex piece. We wish to allocate them into pieces so that the diagonals of different pieces don't intersect.

Lemma: Given $k\ge 2$ points in cyclic order, say that a good allocation is a way of grouping the points together so that no two adjacent points are in the same piece, and given points $p_1,p_2$ in piece $A$ and $q_1,q_2$ in piece $B$, the lines $p_1p_2$ and $q_1q_2$ do not intersect. Then any good allocation uses at least $\left\lfloor \frac k2\right\rfloor +1$ pieces.

For $k=2n$, this will give us the desired result.

Proof: By induction on $k$. Obviously, it is true when $k=2$. Now, suppose it holds up to $k$, and consider a good allocation of $k+1$ points. If no two points are in the same piece, we have $k+1\ge\left\lfloor \frac k2\right\rfloor +1$ pieces.

Otherwise, suppose two points $P$ and $Q$ are in the same piece. Let there be $a$ and $b$ points on either side of the line $PQ$, with $a+b=k-1$. By assumption, $P$ and $Q$ are not adjacent, so $a,b\ge 1$. But then we can think of $PQ$ as a single new "point", $R$, and apply the lemma to the $a+1$ points on one side and the $b+1$ points on the other. We conclude that there are at least $\left\lfloor \frac {a+1}2\right\rfloor +\left\lfloor \frac {b+1}2\right\rfloor +2$ pieces, except we have to subtract $1$ to avoid overcounting the piece containing $PQ$. But

$$\left\lfloor \frac {a+1}2\right\rfloor +\left\lfloor \frac {b+1}2\right\rfloor +1 \ge \frac a2+\frac b2+1 = \frac{k+1}2$$

So there are at least $\left\lceil\frac{k+1}2\right\rceil$ pieces. But for integer $k$, $\left\lceil\frac{k+1}2\right\rceil=\left\lfloor \frac k2\right\rfloor +1$, so the proof is complete.