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.

  • 3
    $\begingroup$ 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. $\endgroup$ – fedja May 10 at 22:09

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.