We divide the arrangement into smaller parts where we apply the dual of Lemma 2. The common technique to do that is the so called
cutting, which was introduced by Chazelle, see in [
11]
, about 20 years ago. Here we use a more general result, a theorem of Matousek [
15]
.
Lemma 8
Let
$P$
be a pointset,
$P\subset {\mathbb{R}}^{d},\leftP\right=n,$
and let
$r$
be a parameter,
$1\ll r\ll n.$
Then the set
$P$
can be partitioned into
$t$
sets
${\Delta}_{1},{\Delta}_{2},\dots ,{\Delta}_{t},$
in such a way that
$n/r\le \left{\Delta}_{i}\right\le 2n/r$
for all
$i,$
and any hyperplane crosses no more than
$O\left({r}^{11/d}\right)$
sets, where
$t=O\left(r\right).$
Here we use the
$d=2$
case and we choose the value
$r={\beta}_{k}{n}^{2/3},$
where
${\beta}_{k}$
is a constant, depends on
$k,$
which we will specify later. Let us count the number of incidences along the lines of
$L,$
according to the partition of
$P.$
For a given line
$\xi \in L,$
we count the sum
${\sum}_{i=1}^{t}\lfloor {\Delta}_{i}\cap \xi /k\rfloor ,$
which is not much smaller than the number of incidences on
$\xi $
over
$k$
if
$\xi $
is rich of incidences, say, incident to much more than
${r}^{1/2}k$
points of
$P.$
From the condition of Theorem 1 and the properties of the partition we have the following inequality.
$$\frac{c}{k}{n}^{4/3}\le {\sum}_{\xi \in L}{\sum}_{i=1}^{t}\lfloor \frac{{\Delta}_{i}\cap \xi }{k}\rfloor +\leftL\right{r}^{1/2}$$
Choosing
${\beta}_{k}=\frac{c}{2k},$
the inequality becomes
$$\frac{c{n}^{4/3}}{2k}={c}_{k}{n}^{\frac{4}{3}}\le {\sum}_{\xi \in L}{\sum}_{i=1}^{t}\lfloor \frac{{\Delta}_{i}\cap \xi }{k}\rfloor ={\sum}_{i=1}^{t}{\sum}_{\xi \in L}\lfloor \frac{{\Delta}_{i}\cap \xi }{k}\rfloor .$$
Therefore there is an index
$i$
, such that
$${c}_{k}{n}^{2/3}\le {\sum}_{\xi \in L}\lfloor \frac{{\Delta}_{i}\cap \xi }{k}\rfloor .$$
If
$s=\lfloor \frac{{\Delta}_{i}\cap \xi }{k}\rfloor $
then we can partition the points incident to
$\xi $
into
$r$
consecutive
$k$
tuples. We can break the line into
$r$
$k$
rich line segments and consider them as separate lines. Our combinatorial argument in Lemma 6 is robust enough to allow such modifications. Then we have some
${c}^{\prime}{n}^{2/3}$
$k$
rich lines on
$\left{\Delta}_{i}\right=c\u201d{n}^{1/3}$
points. (Another possible way to show that there are at least
${c}^{\prime}{n}^{2/3}$
$k$
rich lines, is to apply the SzemerédiTrotter theorem, (1), to show that most of the lines are not ”very rich”.) To complete the proof of Theorem 1, we apply the dual statement of Lemma 6.
References

J. Komlós, M. Simonovits, Szemerédi's regularity lemma and its applications in graph theory, in: Combinatorics, Paul Erdős is eighty, Vol. 2 (Keszthely, 1993), 295352, Bolyai Soc. Math. Stud., 2, János Bolyai Math. Soc., Budapest, 1996.

B. Nagle, V. Rödl, M. Schacht, The counting lemma for regular kuniform hypergraphs, to appear, Random Structures and Algorithms.

V. Rödl, J. Skokan, Regularity lemma for kuniform hypergraphs, to appear, Random Structures and Algorithms.

V. Rödl, J. Skokan, Applications of the regularity lemma for uniform hypergraphs, preprint.

K.F. Roth, On certain sets of integers, J. London Math. Soc. 28 (1953), 245–252.

I. Ruzsa, E. Szemerédi, Triple systems with no six points carrying three triangles, Colloq. Math. Soc. J. Bolyai 18 (1978), 939945.

J. Solymosi, Note on a generalization of Roth's theorem, in: Discrete and computational geometry, 825827, Algorithms Combin. 25, Springer Verlag, 2003.

J. Solymosi, A note on a question of Erdős and Graham, Combinatorics, Probability and Computing 13 (2004), 263267.

E. Szemerédi, On sets of integers containing no four elements in arithmetic progression, Acta Math. Acad. Sci. Hungar. 20 (1969), 89104.

E. Szemerédi, Regular partitions of graphs, in ”Problem'es Combinatoires et Th'eorie des Graphes, Proc. Colloque Inter. CNRS,” (Bermond, Fournier, Las Vergnas, Sotteau, eds.), CNRS Paris, 1978, 399401.

B. Chazelle. The Discrepancy Method. Cambridge University Press, 2000.

K. L. Clarkson, H. Edelsbrunner, L. J. Guibas, M. Sharir, and E. Welzl, Combinatorial complexity bounds for arrangements of curves and spheres, Discrete Comput. Geom. 5 (1990), 99–160.

Gy. Elekes, Sums versus products in Number Theory, Algebra and Erdős Geometry, vol 11 of Bolyai Soc. Math. Stud., János Bolyai Math. Soc., Budapest, 2002, pp. 241–290.

Gy. Elekes and Cs. D. Tóth, Incidences of nottoodegenerate hyperplanes, in Proc. 21st ACM Sympos. Comput. Geom. (Pisa, 2005), ACM Press, to appear.

J. Matoušek, Efficient partition trees, Discrete Comput. Geom. 8 (1992), 315–334.

J. Pach and M. Sharir, Geometric incidences, in Towards a Theory of Geometric Graphs, vol. 342 of Contemporary Mathematics, Amer. Math. Soc., Providence, RI, 2004, pp. 185–223.

J. Solymosi and Cs. D. Tóth, Distinct distances in the plane, Discrete Comput. Geom. 25 (2001), 629–634.

E. Szemerédi and W. T. Trotter Jr., Extremal problems in Discrete Geometry, Combinatorica 3 (3–4) (1983), 381–392.

L. A. Székely, Crossing numbers and hard Erdős problems in discrete geometry, Combinatorics, Probability & Computing 6 (3) (1997), 353–358.

W.T. Gowers, Hypergraph regularity and the multidimensional Szemerédi theorem, preprint.

D. de Caen and L. A. Székely, On dense bipartite graphs of girth eight and upper bounds for certain configurations in planar pointline systems, J. Combin. Theory Ser. A. 77 (1997), 268–278.