# Is the cutting lemma true with O(r) lines?

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.

• A random sample of size r would do the trick, I'd think. – Suresh Venkat Feb 14 '12 at 17:29
• I thought choosing a sample of size r was how the cutting lemma was originally proved. But there may be an issue when the arrangement of the sampled lines has cells with many edges — if you choose a canonical triangulation of the cells (e.g. connect each vertex of the cell to the bottom vertex) then each triangle will be intersected by few lines but that's not quite the same as the statement that the whole cell is intersected by few lines. – David Eppstein Feb 14 '12 at 18:35

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.pdf

and 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.

• I don't even know why I post my questions here instead of just simply emailing you... – domotorp Feb 15 '12 at 8:14
• because then others can benefit as well, and Sariel doesn't have to send multiple emails to people. :) – Suresh Venkat Feb 15 '12 at 17:57
• ...because email is work, but this is fun? – Sariel Har-Peled Feb 15 '12 at 21:56

If the $O(r)$ lines you choose must be drawn from the original set of $n$ lines then the answer is no, it's not possible. In particular if you take $n$ lines tangent to a circle, and then choose any $r$ of them, the region containing the circle will still be intersected by all $n$ of the lines.