Partitioning the plane into subsets with restricted number of intersection with lines

Question

Suppose there are $n$ points in the plane. So there are $O(n^2)$ lines generating by these points. I would like to partition the plane into some subsets such that each subset of points intersected by a few number of lines. I was wondering if there is any theorem about this?

Answer 1

Is this the type of result you seek? Partition the plane into triangles none of which meet too many of the given lines. More precisely,

In this paper we consider the following problem: Given a set ℒ of $n$ lines in the plane, partition the plane into $O(r^2)$ triangles so that no triangle meets more than $O(n/r)$ lines of ℒ. We present a deterministic algorithm for this problem with $O(nr \log n \log^\omega r)$ running time, where $\omega$ is a constant $<3.33$.

Note above $n$ is the number of lines, whereas in your notation $n$ is the number of points which determine up to $\binom{n}{2}$ lines.

Agarwal, Pankaj K. "Partitioning arrangements of lines I: An efficient deterministic algorithm." Discrete & Computational Geometry 5.1 (1990): 449-483. (Journal link.)

---

         

---