The cutting lemma (a.k.a. cell decomposition lemma) states that given $n$ lines in the plane it is possible to divide it into $O(r^2)$ regions (even triangles) for any $1\le r\le n$ such that the interior of any region is intersected by $O(n/r)$ lines. For more see e.g. Matousek's book Lectures on Discrete Geometry or this post.My question is whether the plane can be divided by $O(r)$ lines (into $O(r^2)$ regions) such that the interior of any region is intersected by $O(n/r)$ of the original lines.
Is the cutting lemma true with O(r) lines?
co.combinatorics;cg.comp geom
So, assume you build you vertical decomposition by taking the $O(r)$ lines, taking their arrangement, and then computing its vertical decomposition. The question is there a set of $O(r)$ lines of the original set of lines such that this vertical decomposition form a $1/r$-cutting. Now, if you take Noga Alon's construction in this paper:www.math.tau.ac.il/~nogaa/PDFS/epsnet3.pdfand dualize it, you get a set of lines, such that if a point is contained in more than $n/r$ lines, than one of the lines must belong to the $1/r$-net of the lines. This construction however shows that any net, must be of size strictly super linear in $O(r)$. Noga's result also holds for the weak $\epsilon$-net version. Which shows that there is no set of any lines that would have the desired property.