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