.
For an
$u\in {U}_{F}$
, we denote by
${\pi}_{F}\left(u\right)$
the set of point pairs
$(p,q)\in \pi (p,q)$
such that
$u\cup \{p,q\}$
spans
$F$
. By construction,
$F$
intersects at most
$O\left(m\right)$
subsets
${R}_{i}$
of the partition associated with
$u$
. If the constant
$\gamma $
is sufficiently large, then the average number of points of
${P}_{F}\left(u\right)\cap {R}_{i}$
over the regions
${R}_{i}$
intersecting
$F$
is at least
$4$
. Any two points in
${P}_{F}\left(u\right)\cap {R}_{i}$
determine a pair of
${\pi}_{F}\left(u\right)$
, and so
$$\left{\pi}_{F}\right(u\left)\right\ge {\sum}_{{R}_{i}\cap F\ne \varnothing}\left(\genfrac{}{}{0ex}{}{\left{P}_{F}\right(u)\cap {R}_{i}}{2}\right)\ge \left(\genfrac{}{}{0ex}{}{\left{P}_{F}\right(u\left)\right/O\left(m\right)}{2}\right){\sum}_{{R}_{i}\cap F\ne \varnothing}1\ge \Omega \left(m\right).$$
We can now give a lower bound for
$\leftT\right$
. There are
${f}_{d,k}(n,m)$
distinct
$m$
rich
$k$
flats. Each such
$k$
flat
$F$
contains
$\left{U}_{F}\right\ge \Omega \left({m}^{k1}\right)$
affine independent subsets of size
$k1$
for which
$\left{P}_{F}\right(u\left)\right\ge \Omega \left(m\right)$
. For each such
$u\in {U}_{F}$
, we have
$\left{\pi}_{F}\right(u\left)\right\ge \Omega \left(m\right)$
. Therefore,
$$\leftT\right\ge {f}_{d,k}(n,m)\cdot \Omega \left({m}^{k1}\right)\cdot \Omega \left(m\right)\ge {f}_{d,k}(n,m)\cdot \Omega \left({m}^{k}\right).$$
By contrasting the lower and upper bounds for
$\leftT\right$
, we obtain
$${f}_{d,k}(n,m)\cdot \Omega \left({m}^{k}\right)\le O\left(\frac{{n}^{k+1}}{{m}^{dk+1}}\right),$$
$${f}_{d,k}(n,m)\le O\left(\frac{{n}^{k+1}}{{m}^{d+1}}\right),$$
as required.
$\square $
Corollary 6
For every
$d,k\in \mathbb{N}$
,
$1\le k<d$
, the number of incidences of points and
$m$
rich
$k$
flats in a homogeneous set of
$n$
points in
${\mathbb{R}}^{d}$
is at most
$$O\left(\frac{{n}^{k+1}}{{m}^{d}}\right).$$
Proof. In any homogeneous point set of size
$n$
in
${\mathbb{R}}^{d}$
, the number of incidences is bounded by
$${\sum}_{j=m}^{n}{f}_{d,k}(P,j)\le {\sum}_{j=m}^{n}O\left(\frac{{n}^{k+1}}{{j}^{d+1}}\right)\le O\left(\frac{{n}^{k+1}}{{m}^{d}}\right).$$
$\square $
3 Proof of Theorem 1
We are given a homogeneous set
$P$
of
$n$
points in
${\mathbb{R}}^{d}$
. We may assume without loss of generality that every coordinate of every point in
$P$
is irrational, while the enclosing cube
$C$
has rational coordinates. Let
$t$
denote the maximum number of distinct distances measured from a point of
$P$
(including distance
$0$
). For every
$p\in P$
, the points of
$P$
lie on
$t$
concentric spheres centered at
$p$
.
We subdivide
$C$
into
${s}^{d}$
congruent subcubes
${C}_{1},{C}_{2},\dots ,{C}_{{s}^{3}}$
, where
$$s=\lfloor {\left(\frac{n}{8t}\right)}^{\frac{1}{d1}}\rfloor .$$
Every hyperplane and every sphere intersects the interior of at most
$2{s}^{d1}=O\left(\frac{n}{t}\right)$
subcubes.
Let
$T$
be a set of triples
$(p,q,c)\in {P}^{3}$
such that

(i)
$p\ne q$
,

(ii)
$p$
and
$q$
lie in a subcube
${C}_{i}$
for some
$1\le i\le {s}^{3}$
,

(iii)
$p$
and
$q$
are equidistant from
$c$
.
All points are located on
$nt$
spheres centered at the
$n$
points of
$P$
. There are
${n}^{2}$
spherepoint incidences. The cubes
${C}_{i}$
,
$1\le i\le {s}^{3}$
, subdivide each sphere into patches. Since every sphere intersects at most
$2{s}^{d1}$
subcubes
${C}_{i}$
, there are at most
$2nt{s}^{d1}={n}^{2}/4$
patches, where each patch lies entirely in a subcube
${C}_{i}$
. The average number of points on a patch is at least
$4$
. If
$x$
points lie on a sphere patch centered at
$c$
, then this patch contributes
$\left(\genfrac{}{}{0ex}{}{x}{2}\right)2!$
triples
$(p,q,c)$
to
$T$
. We conclude that the number of triples is
$\leftT\right\ge \Omega \left({n}^{2}\right)$
.
For every
$m\in \mathbb{N}$
, let
${T}_{m}$
denote the set of triples
$(p,q,c)\in T$
such that the bisector hyperplane of the segment
$pq$
is incident to at least
$m$
but less then
$2m$
points of
$P$
. Since every bisector plane is incident to less than
$n$
points, we can partition
$T$
into
$logn$
subsets
$$T{=}^{logn}{\bigcup}_{j=0}{T}_{{2}^{j}}.$$
There is a value
$m={2}^{j}$
for some
$0\le j\le logn$
, such that
$\left{T}_{m}\right\ge \leftT\right/logn\ge \Omega ({n}^{2}/logn)$
.
For a pair
$(p,q)\in {P}^{2}$
,
$p\ne q$
, all points of the set
$M(p,q)=\{c\in P:dist(p,c)=dist(q,c\left)\right\}$
lie on the bisector hyperplane of the line segment
$pq$
. One bisector hyperplane intersects at most
${s}^{d1}$
subcubes, and in each subcube
${C}_{i}$
it can bisect at most
${C}_{i}\cap P/2$
point pairs. So the number of pairs
$(p,q)\in {P}^{2}$
bisected by the same hyperplane is at most
$${s}^{d1}\cdot O\left(\frac{n}{{s}^{d}}\right)=O\left(\frac{n}{s}\right).$$
Let
${B}_{m}$
denote the set of all bisector hyperplanes that bisect the pair
$(p,q)$
for some
$(p,q,c)\in {T}_{m}$
. By definition, any hyperplane in
${B}_{m}$
is incident to at least
$m$
but less than
$2m$
points of
$P$
. By Lemma 5 , we have
$$\left{B}_{m}\right\le O\left(\frac{{n}^{d}}{{m}^{d+1}}\right).$$
We can now give an upper bound for
$\left{T}_{m}\right$
. In a triple
$(p,q,c)\in {T}_{m}$
, point
$c$
lies on a bisector hyperplane of
${B}_{m}$
. Each bisector hyperplane is incident to less than
$2m$
points of
$P$
and bisects at most
$O(n/s)$
pairs
$(p,q)$
. Therefore
$$\Omega \left(\frac{{n}^{2}}{logn}\right)\le \left{T}_{m}\right\le O\left(\frac{{n}^{d}}{{m}^{d+1}}\right)\cdot 2m\cdot O\left(\frac{n}{s}\right),$$
$${m}^{d}\le O\left(\frac{{n}^{d1}}{slogn}\right),$$
$$\begin{array}{c}m\le O\left(\frac{{n}^{\frac{d1}{d}}}{{s}^{1/d}{log}^{1/d}n}\right).\end{array}$$ 
(1)

We obtain another upper bound for
$\left{T}_{m}\right$
by the following argument: In a triple
$(p,q,c)\in {T}_{m}$
, both
$p$
and
$q$
lie in the same subcube
${C}_{i}\subset C$
. There are
${s}^{d}$
subcubes, and each subcube contains less than
$\left(O\right(n/{s}^{d}){)}^{2}\le O({n}^{2}/{s}^{2d})$
point pairs. Hence, there are less than
${s}^{d}\cdot O({n}^{2}/{s}^{2d})=O({n}^{2}/{s}^{d})$
such pairs
$(p,q)$
. For each pair
$(p,q)$
, where
$(p,q,c)\in {T}_{m}$
, there are at most
$2m$
points
$c\in P$
on the bisector hyperplane of
$pq$
. We conclude that
$$\Omega \left(\frac{{n}^{2}}{logn}\right)\le \left{T}_{m}\right\le O\left(\frac{{n}^{2}}{{s}^{d}}\right)\cdot 2m.$$
Using the upper bound for
$m$
from Inequality ( 1 ), we have
$${s}^{\frac{{d}^{2}+1}{d}}\le O\left({n}^{\frac{d1}{d}}\cdot {log}^{\frac{d1}{d}}n\right),$$
$${\left(\frac{n}{t}\right)}^{\frac{{d}^{2}+1}{d(d1)}}\le O\left({n}^{\frac{d1}{d}}\cdot {log}^{\frac{d1}{d}}n\right),$$
$$\Omega \left({n}^{\frac{2}{d1}}{log}^{\frac{1d}{d}}n\right)\le {t}^{\frac{{d}^{2}+1}{d(d1)}},$$
$$\Omega \left({n}^{\frac{2d}{{d}^{2}+1}}{log}^{\frac{(d1{)}^{2}}{{d}^{2}+1}}n\right)\le t,$$
as required. This completes the proof of Theorem 1
$\square $
4 Proof of Theorem 2
Consider a homogeneous set
$P$
of
$n$
points in
${\mathbb{R}}^{3}$
. Similarly to the previous section, we assume that all coordinates of every point in
$P$
are irrational, and the vertices of the bounding cube
$C$
have integer coordinates. We subdivide
$C$
into
${s}^{3}$
congruent cubes
${C}_{1},{C}_{2},\dots ,{C}_{{s}^{3}}$
, for
$$s=\lfloor \sqrt{\frac{n}{\gamma t}}\rfloor ,$$
where
$\gamma >0$
is a constant to be specified later.
By Theorem
3 ,
$P\subset {\mathbb{R}}^{3}$
contains
$\Omega \left({n}^{2}\right)$
affine independent point pairs.
This implies that there is a subset
${P}_{0}\subset P$
such that
$\left{P}_{0}\right\ge \Omega \left(n\right)$
and every
$c\in {P}_{0}$
is incident to
$\Omega \left(n\right)$
distinct lines spanned by
$P$
. For every
$c\in {P}_{0}$
, let
$P\left(c\right)\subset P\backslash \left\{c\right\}$
be a set of
$\Omega \left(n\right)$
points such that the lines
$cp$
,
$p\in P\left(c\right)$
, are distinct. For every point
$c\in {P}_{0}$
, let
${H}_{c}$
be a unit sphere centered at
$c$
.
We project the points of
$P\left(c\right)$
into
$\Omega \left(n\right)$
distinct point in
${H}_{p}$
, we denote by
$\hat{p}=cp\cap {H}_{c}$
the projection of
$p\in P\left(c\right)$
. The set of projections to is let
$$\hat{P}\left(c\right):=\{\hat{p}:c\in P(p\left)\right\}.$$
We consider a simplicial partition for
$\hat{P}\left(c\right)$
defined as follows.
Definition 7
Given a set
$\hat{P}$
points on a sphere
${\mathbb{S}}^{2}$
and an integer
$s$
, the simplicial partition of
$\hat{P}$
is a partition of
$\hat{P}$
into
$O\left({s}^{2}\right)$
sets
${\hat{P}}_{1},{\hat{P}}_{2},\dots ,{\hat{P}}_{\Theta \left({s}^{2}\right)}$
with the following properties

∙
for every
$i$
,
${\hat{P}}_{i}$
lies in set
${R}_{i}\subset {\mathbb{S}}^{2}$
whose boundary consists of a finite number of circular arcs;

∙
for every
$i$
,
$n/{s}^{2}\le \left{\hat{P}}_{i}\right\le n/2{s}^{2}$
;

∙
every circle in
${\mathbb{S}}^{2}$
crosses at most
$O\left(s\right)$
sets
${R}_{i}$
.
A circle crosses a set
${R}_{i}$
, if it intersects it but does not contain it.
By a result of Matoušek [
17,
5]
, there exists a simplicial partition for any
$\hat{P}\subset {\mathbb{S}}^{2}$
and
$1\le {s}^{\prime}\le \left\hat{P}\right$
. (A general result of Matoušek applies: The range space of disks in
${\mathbb{S}}^{2}$
have the properties that its primal shatter function is quadratic and every disk can be approximated with a finite set of ranges with respect to a finite point set.) We consider a simplicial partition for
$\hat{P}\left(c\right)\subset {H}_{c}$
with integer
${s}^{\prime}=s$
.
Let
$Q$
be a set of quadruples
$(p,q,r,c)\in {P}^{4}$
such that,

(i)
the points
$p$
,
$q$
, and
$r$
are distinct;

(ii)
$p,q$
, and
$r$
lie in a subcube
${C}_{i}$
for some
$1\le i\le {s}^{3}$
,

(iii)
$\hat{p},\hat{q}$
, and
$\hat{r}$
lie in a subset
${\hat{P}}_{j}\left(c\right)$
, for some
$1\le j\le \Theta \left({s}^{2}\right)$
, when projected from center
$c$
;

(iv)
$p,q$
, and
$r$
are equidistant from
$c$
.
We give a lower bound on the number of quadruples in
$Q$
. Consider a sphere
$S$
centered at
$c\in {P}_{0}$
. We partition the point set
$P\left(c\right)\cap S$
into groups in the following way. Two points of
$P\left(c\right)\cap S$
are in the same group if and only if they are in the same cube
${C}_{i}$
,
$1\le i\le {s}^{3}$
, and their projections with respect to
$c$
are in the same subset
${\hat{P}}_{j}\left(c\right)$
. We can partition
$C$
into the subcubes
${C}_{i}$
,
$1\le i\le {s}^{3}$
, by
$3(s1)$
planes. These planes partition the sphere
$S$
along
$3(s1)$
circles. Every circle intersects at most
$O\left(s\right)$
regions
${R}_{j}\subset S$
,
$1\le j\le \Theta \left({s}^{2}\right)$
. If
${x}_{j}$
circles intersect a region
${R}_{j}$
, they can partition
${R}_{j}$
into
$O\left({x}_{j}^{2}\right)$
pieces. Hence, the number of groups
$P\left(c\right)\cap S$
is partitioned into is at most
$${\sum}_{j=1}^{\Theta \left({s}^{2}\right)}O\left({x}_{j}^{2}\right)\le \frac{1}{\Theta \left({s}^{2}\right)}\cdot {\left({\sum}_{j=1}^{\Theta \left({s}^{2}\right)}{x}_{j}\right)}^{2}\le \frac{1}{\Theta \left({s}^{2}\right)}\cdot {\left(3(s1)O\left(s\right)\right)}^{2}\le O\left({s}^{2}\right).$$
On the
$\Theta \left(nt\right)$
spheres centered at points of
${P}_{0}$
, we have a total of at most
$O\left(nt{s}^{2}\right)$
groups. We choose constant
$\gamma >0$
(in the definition of
$s$
) such that a group contains
$6$
points on average. If
$x$
points lie on a group, then this group contributes
$\left(\genfrac{}{}{0ex}{}{x}{3}\right)3!$
quadruples
$(p,q,r,c)$
to
$Q$
. We conclude that the total number of quadruples is
$\leftQ\right\ge \Omega \left({n}^{2}\right)$
.
The
multiplicity of a pair
$(p,q)\in {P}^{2}$
is defined as
$$m(p,q)=\left\right\{(p,q,r,c)\in Q:r\in P,c\in {P}_{0}\left\}\right.$$
We choose a parameter
$m$
to be specified later, and distinguish two types of quadruples in
$Q$
: A quadruple
$(p,q,r,c)$
is low if at least one edge of the triangle
$pqr$
have multiplicity at most
$m$
. A quadruple
$(p,q,r,c)$
is high if the multiplicity of all three edges of
$pqr$
are above
$m$
. Let
${Q}^{}$
and
${Q}^{+}$
denote the sets of low and high quadruples, respectively. We distinguish two cases:
First we consider the case that
$\left{Q}^{+}\right\le \left{Q}^{}\right$
, then we proceed with the case
$\left{Q}^{+}\right\ge \left{Q}^{}\right$
.
Case
$\left{Q}^{+}\right\le \left{Q}^{}\right$
. There are at least
$\Omega \left({n}^{2}\right)$
low quadruples in
$Q$
. We define a set of triples
$${T}_{g}:=\left\{\right(p,q,c):(p,q,r,c)\in {Q}^{},m(p,q)\le m\}.$$
We have extracted
$\left{T}_{g}\right\ge \Omega \left({n}^{2}\right)$
triples from
${Q}^{}$
. Similarly, to the previous section, we compute an upper bound on
$\left{T}_{g}\right$
. Every pair
$(p,q)$
from a triple of
${T}_{g}$
lies in one of the
${s}^{3}$
subcubes of
$C$
, and for every pair
$(p,q)$
there are at most
$m$
centers
$c$
. Therefore, we have an upper bound
$$\Omega \left({n}^{2}\right)\le \left{T}_{g}\right\le {s}^{3}{\left(O\left(\frac{n}{{s}^{3}}\right)\right)}^{2}m,$$
$$\Omega \left({s}^{3}\right)\le m,$$
$$\begin{array}{c}\Omega \left(\frac{{n}^{3/2}}{{t}^{3/2}}\right)\le m.\end{array}$$ 
(2)

$$\Omega \left(\frac{n}{{m}^{2/3}}\right)\le t.$$
Case
$\left{Q}^{+}\right\ge \left{Q}^{}\right$
. At least half of the quadruples in
$Q$
are high, and so
$\left{Q}^{+}\right\ge \Omega \left({n}^{2}\right)$
. For every
$c\in {P}_{0}$
, project the points
$P\left(p\right)$
to the sphere
${H}_{c}$
. We denote by
$\hat{p}$
the projection
$\hat{p}=cp\cap {H}_{c}$
of a point
$p\in P\left(p\right)$
. If
$(p,q,r,c)\in Q$
, then the intersection of the bisector plane of
$pq$
and
${H}_{c}$
is the bisector (great circle) of the segment
$\hat{p}\hat{q}$
in the sphere
${H}_{p}$
. A (possibly degenerate) triangle
$\hat{p}\hat{q}\hat{r}$
defines three distinct bisectors. The bisectors of a triangle
$\hat{p}\hat{q}\hat{r}$
meet in two antipodal points on the sphere. The triangles that determine the same triple of bisectors are similar (the center of similarity is the intersection of the bisectors). Specifically, if the triangles
${\hat{p}}_{1}{\hat{q}}_{1}{\hat{r}}_{1},{\hat{p}}_{2}{\hat{q}}_{2}{\hat{r}}_{2},\dots ,{\hat{p}}_{\ell}{\hat{q}}_{\ell}{\hat{r}}_{\ell}$
determine the same triple of bisectors, then the points
${\hat{p}}_{1},{\hat{p}}_{1},\dots ,{\hat{p}}_{\ell}$
are collinear (the points
${\hat{q}}_{1},{\hat{q}}_{1},\dots ,{\hat{q}}_{\ell}$
and
${\hat{r}}_{1},{\hat{r}}_{1},\dots ,{\hat{r}}_{\ell}$
are also collinear). Every triple of bisectors determines a family of triangles. A family of quadruples is a collection of quadruples
$(p,q,r,c)\in {Q}^{+}$
with a common center
$c$
if the triangles
$\hat{p}\hat{q}\hat{r}$
form a family.
For every
$\mu \in \mathbb{N}$
, let
${Q}_{\mu}^{+}$
denote the set of high quadruples
$(p,q,r,c)\in {Q}^{+}$
such that the triangle
$\hat{p}\hat{q}\hat{r}$
on the sphere
${H}_{c}$
is part of a family of size at least
$\mu $
but less than
$2\mu $
. Since the size of any family is less than
$n/3$
, we can partition
${Q}^{+}$
into
$logn$
subsets
$${Q}^{+}{=}^{logn}{\bigcup}_{j=0}{Q}_{{2}^{j}}^{+}.$$
There is a value
$\mu ={2}^{j}$
,
$0\le j\le logn$
, such that
$\left{Q}_{\mu}^{+}\right\ge \left{Q}^{+}\right/logn\ge \Omega ({n}^{2}/logn)$
.
Next, we derive an upper bound for the parameter
$\mu $
. Each quadruple
$(p,q,r,c)\in {Q}_{\mu}^{+}$
uniquely determine a family
$f(p,q,r,c)$
of quadruples of size at least
$\mu $
and at most
$2\mu $
. There are
$\Omega ({n}^{2}/\mu logn)$
disjoint quadruple families in
${Q}_{\mu}^{+}$
. A family
$f(p,q,r,c)$
corresponds to at least
$\mu $
spherical triangles on spheres centered at
$c$
such that their
$3\mu $
vertices lie on three planes incident to
$c$
. For
$\mu \ge 4$
, we call one of these planes a plane spanned by the family.
We denote by
$L$
the set of pairs
$(c,F)$
such that
$c\in {P}_{0}$
and
$F$
is a plane spanned by a family of triangles on spheres centered at
$c$
. Note, though, that several families of triangles with a common center
$c$
can span the same plane
$F$
. Let
${L}_{\lambda}\subset L$
denote the set of pairs
$(c,F)$
such that
$F$
is spanned by at least
$\lambda $
but less than
$2\lambda $
families in
${Q}_{\mu}^{+}$
centered at
$c\in {P}_{0}$
. There is a value
$\lambda ={2}^{k}$
,
$0\le k\le logn$
, such that the pairs in
${L}_{\lambda}$
correspond to at least
$\Omega ({n}^{2}/\mu {log}^{2}n)$
quadruple families of
${Q}_{\mu}^{+}$
. Since each pair
$(c,F)\in {L}_{\lambda}$
belongs to at least
$\lambda $
families, the number of pointplane pairs in
${L}_{\lambda}$
is at least
$\left{L}_{\lambda}\right\ge \Omega ({n}^{2}/\lambda \mu {log}^{2}n)$
.
The pair
$(c,F)\in {L}_{\lambda}$
is an incidence between the point
$c\in P$
and a
$\left(\lambda \mu \right)$
rich plane
$F$
. All incidences are distinct. By Corollary 6 , we have an upper bound on incidences of
$\left(\lambda \mu \right)$
rich planes in a homogeneous set
$P$
:
$$\Omega \left(\frac{{n}^{2}}{\lambda \mu {log}^{2}n}\right)\le \left{L}_{\lambda}\right\le O\left(\frac{{n}^{3}}{(\lambda \mu {)}^{3}}\right),$$
$$(\lambda \mu {)}^{2}\le O(n{log}^{2}n),$$
$$\begin{array}{c}\mu \le O(\sqrt{n}\cdot logn).\end{array}$$ 
(3)

${Q}_{\mu}^{+}$
contains
$\Omega ({n}^{2}/logn)$
quadruples
$(p,q,r,c)$
where
$c$
is a point from the set
${P}_{0}$
of size
$\Omega \left(n\right)$
. There is a set
${P}_{1}\subset {P}_{0}$
of size
$\Omega (n/logn)$
such that each
$c\in {P}_{1}$
is a center of at least
$\Omega (n/logn)$
quadruples of
${Q}_{\mu}^{+}$
. For every
$c\in {P}_{1}$
, we define a set of
$\Omega (n/logn)$
triangles in the sphere
${H}_{c}$
by
$${T}_{c}=\{\hat{p}\hat{q}\hat{r}:(p,q,r,c)\in {Q}_{\mu}^{+}\}$$
For every
$c\in {P}_{1}$
, let
${B}_{c}$
denote the set of
$m$
rich planes incident to
$c$
. Let
${\hat{B}}_{c}$
denote the set of intersections (i.e., great circles) of
${H}_{c}$
and
$m$
rich planes in
${B}_{c}$
. Note that for every edge
$\hat{p}\hat{q}$
of a triangle in
$\hat{P}\left(c\right)$
, the bisector of
$\hat{p}\hat{q}$
is in
${\hat{B}}_{c}$
.
Consider the simplicial partition of the set
$\hat{P}\left(c\right)$
for a point
$c\in {P}_{1}$
. Every set
$\hat{P}\left(c\right)$
,
$i=1,2,\dots ,\Theta \left({s}^{2}\right)$
, contains at most
$O\left(t\right)$
triangles of
${T}_{c}$
. Since there are
$\Theta \left({s}^{2}\right)=\Theta (n/t)$
subsets
${\hat{P}}_{i}\left(s\right)$
and
$\left{T}_{c}\right\le \Omega (n/logn)$
triangles, at least
$\Omega ({s}^{2}/logn)$
subset must contain
$\Omega (t/logn)$
triangles of
${T}_{c}$
. For these sets
${\hat{P}}_{i}\left(c\right)$
, the
$\Omega (t/logn)$
triangles determine at least
$$\Omega \left({\left(\frac{t/logn}{\mu}\right)}^{1/3}\right)$$
distinct bisectors in
${\hat{B}}_{c}$
. A bisector crosses at most
$O\left(s\right)$
regions, and so we obtain the same bisector of
${\hat{B}}_{c}$
in at most
$O\left(s\right)$
regions. We conclude that the number of bisectors determined by the
$\Omega (n/logn)$
triangles of
${T}_{c}$
is
$$\begin{array}{ccc}\left{B}_{c}\right& \ge & \frac{\Theta ({s}^{2}/logn)}{O\left(s\right)}\cdot \Omega \left({\left(\frac{t/logn}{\mu}\right)}^{1/3}\right)\ge \Omega \left(\sqrt{\frac{n}{t}}\cdot \frac{{t}^{1/3}}{{\mu}^{1/3}{log}^{4/3}n}\right)\ge \end{array}$$  
$$\begin{array}{ccc}& \ge & \Omega \left(\frac{{n}^{1/2}}{{t}^{1/6}{\mu}^{1/3}{log}^{4/3}n}\right).\end{array}$$  
Using the estimate
$\mu \le O(\sqrt{n}\cdot logn)$
from Inequality ( 3 ), we obtain that
$$\left{B}_{c}\right\ge \Omega \left(\frac{{n}^{1/3}}{{t}^{1/6}{log}^{5/3}n}\right).$$
Each of the
$\Omega (n/logn)$
points of
${P}_{1}$
is incident to
$\Omega ({n}^{1/3}/{t}^{1/6}{log}^{5/3}n)$
distinct
$m$
rich planes. This gives
$\Omega ({n}^{4/3}/{t}^{1/6}{log}^{8/3}n)$
incidences on
$m$
rich planes of
$P$
. By Corollary 6 , we have
$$\Omega \left(\frac{{n}^{4/3}}{{t}^{1/6}{log}^{8/3}n}\right)\le O\left(\frac{{n}^{3}}{{m}^{3}}\right),$$
$${m}^{3}\le O\left({n}^{5/3}{t}^{1/6}{log}^{8/3}n\right),$$
$$\begin{array}{c}m\le O\left({n}^{5/9}{t}^{1/18}{log}^{8/9}n\right).\end{array}$$ 
(4)

$$\Omega \left(\frac{{m}^{18}}{{n}^{10}{log}^{16}n}\right)\le t.$$
In both cases, we have derived lower bounds for
$t$
in terms of
$n$
and
$m$
.
We choose
$m\in \mathbb{N}$
such that we obtain the same result in both cases. By comparing Inequalities ( 2 ) and ( 4 ), we have
$$\Omega \left(\frac{{n}^{3/2}}{{t}^{3/2}}\right)\le m\le O\left({n}^{5/9}{t}^{1/18}{log}^{8/9}n\right),$$
$$\Omega \left(\frac{{n}^{17/18}}{{log}^{8/9}n}\right)\le {t}^{28/18},$$
$$\begin{array}{c}\Omega \left(\frac{{n}^{17/28}}{{log}^{4/7}n}\right)\le t.\end{array}$$ 
(5)

The choice
$m=\lfloor {n}^{33/56}{log}^{12/14}n\rfloor $
establishes Inequality ( 5 ) in both cases.
This completes the proof of Theorem
2
$\square $
References

P. K. Agarwal and B. Aronov, Counting facets and incidences, Discrete Comput. Geom. 7 (1992) 359–369.

B. Aronov, J. Pach, M. Sharir, and G. Tardos, Distinct distances in three and higher dimensions, Combin. Probab. Comput. 13 (2004), 283–293.

B. Aronov and M. Sharir, Cell complexities in hyperplane arrangements, Discrete Comput. Geom. 32 (2004), 107–115.

J. Beck, On the lattice property of the plane and some problems of Dirac, Motzkin and Erdős, Combinatorica 3 (34) (1983), 281–297.

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.

H. Edelsbrunner and M. Sharir, A hyperplane incidence problem with applications to counting distances, in Proc. SIGAL International Symposium on Algorithms (T. Asano et al., eds.), vol. 450 of LNCS, SpringerVerlag, Berlin, 1990, pp. 419–428.

Gy. Elekes, A note on the number of distinct distances, Period. Math. Hungar. 38 (1999), 173–177.

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

P. Erdős, On sets of distances of
$n$
points, Amer. Math. Monthly 53 (1946), 248–250.

S. Hofmann and A. Iosevich, Circular averages and FalconerErdős distance conjecture in the plane for random metrics, Proc. Amer. Math. Soc. 133 (1) (2005), 133–143

A. Iosevich, Curvature, combinatorics, and the Fourier transform, Notices Amer. Math. Soc. 48 (2001), 577–583.

A. Iosevich, N. Katz, and S. Pedersen, Fourier basis and the Erdős distance problem, Math. Research Letters 6 (2) (1999), 251–255.

A. Iosevich and I. Łaba, Distance sets of welldistributed planar point sets, Discrete Comput. Geom. 31 (2004), 243–250.

S. Konyagin and I. Łaba, Distance sets of welldistributed planar sets for polygonal norms, Israel J. Math. to appear.

N. H. Katz and G. Tardos, A new entropy inequality for the Erdős distance problem, in: Towards a theory of geometric graphs, vol. 342 of Contemp. Math., Amer. Math. Soc., Providence, RI, 2004, pp. 119–126.

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, G. Tardos, and Cs. D. Tóth, The
$k$
most frequent distances in the plane, Discrete Comput. Geom. 28 (2002), 639–648.

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

J. Solymosi and V. Vu, Distinct distances in high dimensional homogeneous sets, in: Towards a theory of geometric graphs, vol. 342 of Contemp. Math., Amer. Math. Soc., Providence, RI, 2004, pp. 259–268.

J. Solymosi and V. Vu, Near optimal bounds for the Erdős distinct distance problem in high dimensions, Combinatorica to appear.

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.