Balanced convex partitions of lines in the plane

Abstract

We prove an extension of a ham sandwich theorem for families of lines in the plane by Dujmović and Langerman. Given two sets $A,B$ of $n$ lines each in the plane, we prove that it is possible to partition the plane into $r$ convex regions such that the following holds. For each region $C$ of the partition there is a subset of $c_r{n}^{1/r}$ lines of $A$ whose pairwise intersections are in $C$, and the same holds for $B$. In this statement $c_r$ only depends on $r$. We also prove that the dependence on $n$ is optimal.

14 pages, 4 figures