# Decomposing a convex quadrilateral

Problem: Let $$Q$$ be a convex quadrilateral which is cut into convex pieces (cells) by a finite number of lines. For any collection $$(Q_i)_1^n$$ of these cells, decompose $$Q$$ into nonoverlapping convex polygons $$(R_i)_1^n$$ so that $$Q_i \subset R_i$$ for every $$i$$, and $$\sum s_i \le 4n$$, where $$s_i$$ denotes the number of sides of $$R_i$$.

This is a technical lemma I need for a separate problem, but I can really make progress on it.

• Just notice that if you have a partition into convex cells and split one of them by a line into two cells, the total number of cell sides goes up by at most $4$ (two sides get split into $2$ and the new separating side is counted twice). Now take any 2 $Q_i$'s, separate them by some line you used in the original partition (so that every other $Q_j$ lies on one side of that line) and continue that process in each half separately. – fedja May 10 at 22:09

## 1 Answer

Note the following:

1. Dissecting a convex polygon with a straight line produces two convex polygons.

2. For any two cells in $$Q$$, at least one of the original cutting lines separates the two cells from each other.

Using these two observations, we can recursively subdivide $$Q$$ using the following procedure:

Choose any two of the $$Q_i$$, then choose any cutting line which separates them. This line separates $$Q$$ into two convex regions. If any of these two regions contains more than one of the $$Q_i$$ then we again choose two of the $$Q_i$$ which are contained within the offending region, choose a cutting line separating them and subdivide this region with the chosen line. Continue until all regions contain only one of the $$Q_i$$.

Fedja's comment explains why $$\sum s_i\le 4n$$ for the resulting decomposition.