<p>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. </p>

<p>Now, if you take Noga Alon's construction in this paper:</p>

<p>www.math.tau.ac.il/~nogaa/PDFS/epsnet3.pdf</p>

<p>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.</p>

CC BY-SA 3.0
2012-02-15T08:14:46.453Z
I don't even know why I post my questions here instead of just simply emailing you...
domotorp
CC BY-SA 3.0
2012-02-15T17:57:29.743Z
because then others can benefit as well, and Sariel doesn't have to send multiple emails to people. :)
Suresh Venkat
CC BY-SA 3.0
2012-02-15T21:56:32.903Z
...because email is work, but this is fun?
Sariel Har-Peled
CC BY-SA 3.0
2012-02-15T01:00:57.093Z
2012-02-15T01:00:57.093Z
Sariel Har-Peled
<p>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.</p>

CC BY-SA 3.0
2012-02-14T20:39:54.273Z
2012-02-14T20:39:54.273Z
David Eppstein
<p>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 <a href="http://terrytao.wordpress.com/2009/06/12/the-szemeredi-trotter-theorem-and-the-cell-decomposition/">this post</a>.</p>

<p>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.</p>

CC BY-SA 3.0
2012-02-14T17:29:17.287Z
A random sample of size r would do the trick, I'd think.
Suresh Venkat
CC BY-SA 3.0
2012-02-14T18:35:23.133Z
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
<co.combinatorics><cg.comp-geom>
Is the cutting lemma true with O(r) lines?
domotorp
# Is the cutting lemma true with O(r) lines?

(Asked by: username_0 on 2012-02-14)

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](http://terrytao.wordpress.com/2009/06/12/the-szemeredi-trotter-theorem-and-the-cell-decomposition/).

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.

**Tags:** co.combinatorics, cg.comp-geom

> **Comments:**
> **username_1**: A random sample of size r would do the trick, I'd think.  
> **username_2**: 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.  

---

## 2 answers

### Answer by username_3 on 2012-02-15. Score: 7 | Accepted answer

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.

> **Comments:**
> **username_0**: I don't even know why I post my questions here instead of just simply emailing you...  
> **username_1**: because then others can benefit as well, and Sariel doesn't have to send multiple emails to people. :)  
> **username_3**: ...because email is work, but this is fun?  

---

### Answer by username_2 on 2012-02-14. Score: 7

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.


---

