On distinct distances in homogeneous sets in the Euclidean space

József SolymosiDepartment of Mathematics, University of British Columbia, Vancouver, BC, Canada V6T 1Z2, Email: solymosi@math.ubc.ca The research was supported by OTKA and NSERC grants.

Csaba D. TóthDepartment of Mathematics, MIT, Cambridge, MA 02139, USA, Email: toth@math.mit.edu

Abstract
A homogeneous set of n   points in the d   -dimensional Euclidean space determines at least Ω ( n 2 d / ( d 2 + 1 ) / log c ( d ) n )   distinct distances for a constant c ( d ) > 0   . In three-space, we slightly improve our general bound and show that a homogeneous set of n   points determines at least Ω ( n . 6071 )   distinct distances.

1 Introduction

The history of the distinct distance problem goes back to Erdős [10] who asked the question: What is the minimal number g d ( n )   of distinct distances determined by n   points in the d   -dimensional Euclidean space R d   ? The example of n   points in the d   -dimensional integer grid [ 1 , 2 , … , n 1 d ] d   shows that g d ( n ) ≤ O ( n 2 / d )   for any d ≥ 2   and, in particular, g 2 ( n ) ≤ O ( n / log n )   .
Erdős conjectured that these bounds are essentially optimal.
Research efforts on the distinct distance problem have lead to powerful methods (such as the crossing theory [24] , the ɛ   -cutting theory [6] ) that found innumerable applications in discrete and computational geometry. An excellent survey by Pach and Sharir [18] elaborate on the history of the distinct distance problem and its connections to other fields of discrete mathematics. The currently known best lower bound for the distinct distance problem in the plane, g 2 ( n ) = Ω ( n . 8641 )   , is due to Katz and Tardos [16] . Their proof combines results of Solymosi and Tóth [20] with additive number theory.
In higher dimensions, fewer results are known. Aronov et al. [2] showed that the number of distinct distances determined by a set of n   points in three-dimensional space is Ω ( n 77 / 141 − ɛ ) = Ω ( n . 5460 )   for any ɛ > 0   . Solymosi and Vu [22] proved a general lower bound of Ω ( n 2 / d − 2 / d ( d + 2 ) )   for any d ≥ 4   .
In this paper, we consider the number h d ( n )   of distinct distances in homogeneous sets of n   points in R d   . A finite point set P ⊂ R d   is homogeneous if the following two conditions hold: P   lies in the interior of an axis-aligned d   -dimensional cube C   of volume | P |   , and any unit cube in R d   contains at most O ( 1 )   points of P   . Homogeneous sets represent an important special case for the distinct distance problem because the best known upper bound constructions (the d   -dimensional integer grids) are homogeneous, and because of numerous connections to analysis [13, 11] . Iosevich [12] studied the distinct distance problem for homogeneous sets (with additional restrictions). He showed that h d ( n ) ≥ Ω ( n 3 / 2 d )   for d ≥ 2   . Solymosi and Vu [21] proved a general bound h d ( n ) ≥ Ω ( n 2 / d − 1 / d 2 )   for d ≥ 2   . In the case d = 3   , they have also obtained a slightly better bound h 3 ( n ) ≥ Ω ( n . 5794 )   . In this paper, we improve all previous lower bounds on the number of distinct distances in homogeneous sets of n   points in R d   .
Theorem 1 For any d ∈ N   , every homogeneous set P   of n   points in R d   determines at least h d ( n ) ≥ Ω ( n 2 d d 2 + 1 / log ( d − 1 ) 2 d 2 + 1 n )   distinct distances. Moreover, there is a point p ∈ P   from which there are this many distinct distances to other points of P   .
For d = 3 , 4   , and 5   , our general lower bound is h 3 ( n ) ≥ Ω ( n . 6 )   , h 4 ( n ) ≥ Ω ( n . 4705 )   , and h 5 ( n ) ≥ Ω ( n . 3846 )   . In three-dimensions, we slightly improve on our general bound for h 3 ( n )   and prove the following.
Theorem 2 Every homogeneous set P   of n   points in R 3   determines at least h 3 ( n ) ≥ Ω ( n 17 28 / log 4 7 n ) ≥ Ω ( n . 6071 )   distinct distances. Moreover, there is a point p ∈ P   from which there are this many distinct distances to other points of P   .
We prove Theorem  1 in Section  3 . The proof of Theorem  2 can be found in Section  4 . In the next section, we present a key lemma on the number of k   -flats incident to many points in a homogeneous point set in R d   , for 1 ≤ k < d   .

2 Rich hyperplanes in homogeneous sets

Consider a set P   of n   points in R d   . We say that a k   -flat (a k   -dimensional affine subspace) is m   -rich if it is incident to at least m   points of P   . The celebrated Szemerédi-Trotter Theorem [23] states that for n   points in the plane, the number of m   -rich lines ( 1   -flats) cannot exceed O ( n 2 / m 3 + n / m )   , and this bound is tight in the worst case.
The number of m   -rich k   -flats in R d   has been intensely studied. The Szemerédi-Trotter type results have widespread applications in discrete and combinatorial geometry. The Szemerédi-Trotter Theorem's multi-dimensional generalizations [7, 1, 9] always impose some kind of restriction on the point set or on the set of k   -flats, otherwise m   points on a line give rise to an infinity of m   -rich k   -flats for any 2 ≤ k ≤ d   .
We say that a k   -flat F   is α   -degenerate for a constant α > 0   if any ( k − 1 )   -flat contains no more than α ⋅ | F ∩ P |   points of F ∩ P   . A set of k + 1   points is affine independent if it is contained in a unique k   -flat, which is said to be spanned by the point set. We recall a result of Beck [4] on α   -degenerate hyperplanes.
Theorem 3 (Beck) For any k ∈ N   , there are constants α k , β k > 0   with the following property: Given a point set P ⊂ R d   , if an m   -rich k   -flat F   is α k   -degenerate, then F   contains at least β k ⋅ m k   distinct ( k − 1 )   -flats spanned by P ∩ F   . □  
Elekes and Tóth [9] found that there is a constant γ d > 0   for every dimension d ∈ N   such that the number of m   -rich γ d   -degenerate hyperplanes in R d   is at most O ( n d / m d + 1 + n d − 1 / m d − 1 )   . Here, the second term, O ( n d − 1 / m d − 1 )   , is dominant if m ≥ n   . We show below a much stronger upper bound for homogeneous sets: The number of m   -rich hyperplanes is at most O ( n d / m d + 1 )   .
Let f d , k ( P , m )   denote the maximal number of m   -rich k   -flats in a homogeneous set P   of n   points in R d   , and let f d , k ( n , m ) = max P ⊂ R d , | P | = n f d , k ( P , m ) .   For the number of m   -rich lines in homogeneous sets in R d   (that is, for k = 1   ), Solymosi and Vu [21] established the following lemma.
Lemma 4 (Solymosi & Vu) For every d ∈ N   , the number of m   -rich lines in a homogeneous set of n   points in R d   is bounded by f d , 1 ( n , m ) ≤ O ( n 2 m d + 1 ) .   □  
We extend their result for arbitrary k ∈ N   , 1 ≤ k ≤ d − 1   .
Lemma 5 For every d , k ∈ N   , 1 ≤ k < d   , the number of m   -rich k   -flats in a homogeneous set of n   points in R d   is bounded by f d , k ( n , m ) ≤ O ( n k + 1 m d + 1 ) .  
The example of the d   -dimensional integer grid [ 1 , 2 , … , n 1 d ] d   shows that this bound is best possible for every 1 ≤ m ≤ n k / d   .
Proof. Let P   be a homogeneous set of n   points in R d   for some d ∈ N   . We proceed by induction on k   . The base case, k = 1   , is equivalent to Lemma  4 .
Let us assume that k > 1   and that f d , k ′ ( P , m ) ≤ O ( n k ′ + 1 / m k ′ + 1 )   for every k ′   , 1 ≤ k ′ < k   . We count separately the m   -rich k   -flats that are α k   -degenerate and those that are not.
If an m   -rich k   -flat is not α k   -degenerate, then it contains an ( α k m )   -rich ( k − 1 )   -flat. By induction, the number of ( α k m )   -rich ( k − 1 )   -flats is O ( n k / m d + 1 )   .
Every ( α k m )   -rich ( k − 1 )   -flat F k − 1   can be extended to a (degenerate) m   -rich k   -flat in O ( n )   different ways: F k − 1   together with a point of P \ F k − 1   spans a k   -flat. This gives an upper bound of O ( n k + 1 / m d + 1 )   on the not α k   -degenerate m   -rich k   -flats.
Next, we consider the α k   -degenerate m   -rich k   -flats. Let U   be a family of all affine independent ( k − 1 )   -element subsets of P   . In a homogeneous set of n   points, there are | U | = Θ ( n k − 1 )   such subsets.
For every u ∈ U   , independently, we subdivide R d   into ℓ = γ m d − k + 1   regions, for some constant γ > 0   to be specified later: Let H = H ( u )   denote the ( k − 2 )   -flat spanned by u   , and let H ⊥   denote the ( d − k + 2 )   -flat orthogonal to H   . The set of points in R d   at unit distance from H   is the Minkowski sum S ⊕ H   , where S   is a unit sphere S d − k + 1   in H ⊥   . A projection τ u : R d \ H → S   can be defined as x → τ u ( x ) = S ∩ 〈 H , x 〉   , where 〈 H , x 〉   is the k   -flat spanned by H   and x   . Let us partition S ⊂ H ⊥   into ℓ = γ m d − k + 1   regions S 1 , S 2 , … , S ℓ   such that the regions have the same volume and every 2   -flat through the center of S   (that is, every great circle on the sphere S d − k + 1   ) intersects at most O ( ℓ 1 / ( d − k + 1 ) ) = O ( m )   regions. We then subdivide R d   into ℓ   regions R i   , 1 ≤ i ≤ ℓ   , such that R i = { p ∈ R d : τ u ( p ) ∈ S i } .   Since the ( k − 2 )   -flat H   intersects the cube C   , the intersection R i ∩ C   has volume O ( n / ℓ ) = O ( n / m d − k + 1 )   for every i   . By homogeneity, we have | R i ∩ P | = O ( n / ℓ ) = O ( n / m d − k + 1 )   points of P   in every region R i   . Observe that every k   -flat that contains H   intersects at most O ( m )   regions.
For an u ∈ U   , we estimate the cardinality of the set π ( u )   of point pairs ( p , q ) ∈ P 2   such that
  • ∙ u ∪ { p , q }   is an affine independent set and spans an m   -rich k   -flat of P   ;
  • ∙ p   and q   lie in a region R i   , for some 1 ≤ i ≤ ℓ   .
By counting all pairs { p , q }   satisfying the second condition, we obtain an upper bound for | π ( u ) |   :
| π ( u ) | ≤ ∑ i = 1 ℓ ( | R i ∩ P | 2 ) ≤ O ( m d − k + 1 ) ⋅ ( O ( n m d − k + 1 ) ) 2 ≤ O ( n 2 m d − k + 1 ) .   Let T   be the set of triples ( u , p , q ) ∈ U × P 2   such that u ∈ U   and ( p , q ) ∈ π ( u )   . By combining the upper bounds for | U |   and for π ( u )   , we have | T | ≤ Θ ( n k − 1 ) ⋅ O ( n 2 m d − k + 1 ) ≤ O ( n k + 1 m d − k + 1 ) .   Next, we compute a lower bound for the quantity | T |   . Consider an α k   -degenerate m   -rich k   -flat F   . For a set u   of k − 1   affine independent points in P ∩ F   , let P F ( u )   denote a maximal size subset of P ∩ ( F \ H )   whose elements have distinct projections under τ u   . By Beck's Theorem  3 , there is a family U F ⊂ U   of Ω ( m k − 1 )   subsets u ⊂ P ∩ F   such that the number | P F ( u ) |   of distinct projections under τ u   is at least Ω ( m )   .
For an u ∈ U F   , we denote by π F ( u )   the set of point pairs ( p , q ) ∈ π ( p , q )   such that u ∪ { p , q }   spans F   . By construction, F   intersects at most O ( m )   subsets R i   of the partition associated with u   . If the constant γ   is sufficiently large, then the average number of points of P F ( u ) ∩ R i   over the regions R i   intersecting F   is at least 4   . Any two points in P F ( u ) ∩ R i   determine a pair of π F ( u )   , and so | π F ( u ) | ≥ ∑ R i ∩ F ≠ ∅ ( | P F ( u ) ∩ R i | 2 ) ≥ ( | P F ( u ) | / O ( m ) 2 ) ∑ R i ∩ F ≠ ∅ 1 ≥ Ω ( m ) .   We can now give a lower bound for | T |   . There are f d , k ( n , m )   distinct m   -rich k   -flats. Each such k   -flat F   contains | U F | ≥ Ω ( m k − 1 )   affine independent subsets of size k − 1   for which | P F ( u ) | ≥ Ω ( m )   . For each such u ∈ U F   , we have | π F ( u ) | ≥ Ω ( m )   . Therefore, | T | ≥ f d , k ( n , m ) ⋅ Ω ( m k − 1 ) ⋅ Ω ( m ) ≥ f d , k ( n , m ) ⋅ Ω ( m k ) .   By contrasting the lower and upper bounds for | T |   , we obtain f d , k ( n , m ) ⋅ Ω ( m k ) ≤ O ( n k + 1 m d − k + 1 ) ,   f d , k ( n , m ) ≤ O ( n k + 1 m d + 1 ) ,   as required. □  
Corollary 6 For every d , k ∈ N   , 1 ≤ k < d   , the number of incidences of points and m   -rich k   -flats in a homogeneous set of n   points in R d   is at most O ( n k + 1 m d ) .  
Proof. In any homogeneous point set of size n   in R d   , the number of incidences is bounded by ∑ j = m n f d , k ( P , j ) ≤ ∑ j = m n O ( n k + 1 j d + 1 ) ≤ O ( n k + 1 m d ) .   □  

3 Proof of Theorem  1 

We are given a homogeneous set P   of n   points in 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 ∈ 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 , … , C s 3   , where s = ⌊ ( n 8 t ) 1 d − 1 ⌋ .   Every hyperplane and every sphere intersects the interior of at most 2 s d − 1 = O ( n t )   subcubes.
Let T   be a set of triples ( p , q , c ) ∈ P 3   such that
  • (i) p ≠ q   ,
  • (ii) p   and q   lie in a subcube C i   for some 1 ≤ i ≤ s 3   ,
  • (iii) p   and q   are equidistant from c   .
All points are located on n t   spheres centered at the n   points of P   . There are n 2   sphere-point incidences. The cubes C i   , 1 ≤ i ≤ s 3   , subdivide each sphere into patches. Since every sphere intersects at most 2 s d − 1   subcubes C i   , there are at most 2 n t s d − 1 = 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 ( x 2 ) 2 !   triples ( p , q , c )   to T   . We conclude that the number of triples is | T | ≥ Ω ( n 2 )   .
For every m ∈ N   , let T m   denote the set of triples ( p , q , c ) ∈ T   such that the bisector hyperplane of the segment p q   is incident to at least m   but less then 2 m   points of P   . Since every bisector plane is incident to less than n   points, we can partition T   into log n   subsets T = log n ⋃ j = 0 T 2 j .   There is a value m = 2 j   for some 0 ≤ j ≤ log n   , such that | T m | ≥ | T | / log n ≥ Ω ( n 2 / log n )   .
For a pair ( p , q ) ∈ P 2   , p ≠ q   , all points of the set M ( p , q ) = { c ∈ P : d i s t ( p , c ) = d i s t ( q , c ) }   lie on the bisector hyperplane of the line segment p q   . One bisector hyperplane intersects at most s d − 1   subcubes, and in each subcube C i   it can bisect at most | C i ∩ P | / 2   point pairs. So the number of pairs ( p , q ) ∈ P 2   bisected by the same hyperplane is at most s d − 1 ⋅ O ( n s d ) = O ( n s ) .   Let B m   denote the set of all bisector hyperplanes that bisect the pair ( p , q )   for some ( p , q , c ) ∈ T m   . By definition, any hyperplane in B m   is incident to at least m   but less than 2 m   points of P   . By Lemma  5 , we have | B m | ≤ O ( n d m d + 1 ) .   We can now give an upper bound for | T m |   . In a triple ( p , q , c ) ∈ T m   , point c   lies on a bisector hyperplane of B m   . Each bisector hyperplane is incident to less than 2 m   points of P   and bisects at most O ( n / s )   pairs ( p , q )   . Therefore Ω ( n 2 log n ) ≤ | T m | ≤ O ( n d m d + 1 ) ⋅ 2 m ⋅ O ( n s ) ,   m d ≤ O ( n d − 1 s log n ) ,  
m ≤ O ( n d − 1 d s 1 / d log 1 / d n ) . (1)
We obtain another upper bound for | T m |   by the following argument: In a triple ( p , q , c ) ∈ T m   , both p   and q   lie in the same subcube C i ⊂ C   . There are s d   subcubes, and each subcube contains less than ( O ( n / s d ) ) 2 ≤ O ( n 2 / s 2 d )   point pairs. Hence, there are less than s d ⋅ O ( n 2 / s 2 d ) = O ( n 2 / s d )   such pairs ( p , q )   . For each pair ( p , q )   , where ( p , q , c ) ∈ T m   , there are at most 2 m   points c ∈ P   on the bisector hyperplane of p q   . We conclude that Ω ( n 2 log n ) ≤ | T m | ≤ O ( n 2 s d ) ⋅ 2 m .   Using the upper bound for m   from Inequality ( 1 ), we have s d 2 + 1 d ≤ O ( n d − 1 d ⋅ log d − 1 d n ) ,   ( n t ) d 2 + 1 d ( d − 1 ) ≤ O ( n d − 1 d ⋅ log d − 1 d n ) ,   Ω ( n 2 d − 1 log 1 − d d n ) ≤ t d 2 + 1 d ( d − 1 ) ,   Ω ( n 2 d d 2 + 1 log − ( d − 1 ) 2 d 2 + 1 n ) ≤ t ,   as required. This completes the proof of Theorem  1  □  

4 Proof of Theorem  2 

Consider a homogeneous set P   of n   points in 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 , … , C s 3   , for s = ⌊ n γ t ⌋ ,   where γ > 0   is a constant to be specified later.
By Theorem  3 , P ⊂ R 3   contains Ω ( n 2 )   affine independent point pairs.
This implies that there is a subset P 0 ⊂ P   such that | P 0 | ≥ Ω ( n )   and every c ∈ P 0   is incident to Ω ( n )   distinct lines spanned by P   . For every c ∈ P 0   , let P ( c ) ⊂ P \ { c }   be a set of Ω ( n )   points such that the lines c p   , p ∈ P ( c )   , are distinct. For every point c ∈ P 0   , let H c   be a unit sphere centered at c   .
We project the points of P ( c )   into Ω ( n )   distinct point in H p   , we denote by p ^ = c p ∩ H c   the projection of p ∈ P ( c )   . The set of projections to is let P ^ ( c ) : = { p ^ : c ∈ P ( p ) } .   We consider a simplicial partition for P ^ ( c )   defined as follows.
Definition 7 Given a set P ^   points on a sphere S 2   and an integer s   , the simplicial partition of P ^   is a partition of P ^   into O ( s 2 )   sets P ^ 1 , P ^ 2 , … , P ^ Θ ( s 2 )   with the following properties
  • ∙ for every i   , P ^ i   lies in set R i ⊂ S 2   whose boundary consists of a finite number of circular arcs;
  • ∙ for every i   , n / s 2 ≤ | P ^ i | ≤ n / 2 s 2   ;
  • ∙ every circle in S 2   crosses at most O ( s )   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 P ^ ⊂ S 2   and 1 ≤ s ′ ≤ | P ^ |   . (A general result of Matoušek applies: The range space of disks in 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 P ^ ( c ) ⊂ H c   with integer s ′ = s   .
Let Q   be a set of quadruples ( p , q , r , c ) ∈ 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 ≤ i ≤ s 3   ,
  • (iii) p ^ , q ^   , and r ^   lie in a subset P ^ j ( c )   , for some 1 ≤ j ≤ Θ ( s 2 )   , 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 ∈ P 0   . We partition the point set P ( c ) ∩ S   into groups in the following way. Two points of P ( c ) ∩ S   are in the same group if and only if they are in the same cube C i   , 1 ≤ i ≤ s 3   , and their projections with respect to c   are in the same subset P ^ j ( c )   . We can partition C   into the subcubes C i   , 1 ≤ i ≤ s 3   , by 3 ( s − 1 )   planes. These planes partition the sphere S   along 3 ( s − 1 )   circles. Every circle intersects at most O ( s )   regions R j ⊂ S   , 1 ≤ j ≤ Θ ( s 2 )   . If x j   circles intersect a region R j   , they can partition R j   into O ( x j 2 )   pieces. Hence, the number of groups P ( c ) ∩ S   is partitioned into is at most ∑ j = 1 Θ ( s 2 ) O ( x j 2 ) ≤ 1 Θ ( s 2 ) ⋅ ( ∑ j = 1 Θ ( s 2 ) x j ) 2 ≤ 1 Θ ( s 2 ) ⋅ ( 3 ( s − 1 ) O ( s ) ) 2 ≤ O ( s 2 ) .   On the Θ ( n t )   spheres centered at points of P 0   , we have a total of at most O ( n t s 2 )   groups. We choose constant γ > 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 ( x 3 ) 3 !   quadruples ( p , q , r , c )   to Q   . We conclude that the total number of quadruples is | Q | ≥ Ω ( n 2 )   .
The multiplicity of a pair ( p , q ) ∈ P 2   is defined as m ( p , q ) = | { ( p , q , r , c ) ∈ Q : r ∈ P , c ∈ P 0 } | .   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 p q r   have multiplicity at most m   . A quadruple ( p , q , r , c )   is high if the multiplicity of all three edges of p q r   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 | Q + | ≤ | Q − |   , then we proceed with the case | Q + | ≥ | Q − |   .
Case | Q + | ≤ | Q − |   . There are at least Ω ( n 2 )   low quadruples in Q   . We define a set of triples T g : = { ( p , q , c ) : ( p , q , r , c ) ∈ Q − , m ( p , q ) ≤ m } .   We have extracted | T g | ≥ Ω ( n 2 )   triples from Q −   . Similarly, to the previous section, we compute an upper bound on | T g |   . 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 Ω ( n 2 ) ≤ | T g | ≤ s 3 ( O ( n s 3 ) ) 2 m ,   Ω ( s 3 ) ≤ m ,  
Ω ( n 3 / 2 t 3 / 2 ) ≤ m . (2)
Ω ( n m 2 / 3 ) ≤ t .   Case | Q + | ≥ | Q − |   . At least half of the quadruples in Q   are high, and so | Q + | ≥ Ω ( n 2 )   . For every c ∈ P 0   , project the points P ( p )   to the sphere H c   . We denote by p ^   the projection p ^ = c p ∩ H c   of a point p ∈ P ( p )   . If ( p , q , r , c ) ∈ Q   , then the intersection of the bisector plane of p q   and H c   is the bisector (great circle) of the segment p ^ q ^   in the sphere H p   . A (possibly degenerate) triangle p ^ q ^ r ^   defines three distinct bisectors. The bisectors of a triangle p ^ q ^ 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 p ^ 1 q ^ 1 r ^ 1 , p ^ 2 q ^ 2 r ^ 2 , … , p ^ ℓ q ^ ℓ r ^ ℓ   determine the same triple of bisectors, then the points p ^ 1 , p ^ 1 , … , p ^ ℓ   are collinear (the points q ^ 1 , q ^ 1 , … , q ^ ℓ   and r ^ 1 , r ^ 1 , … , r ^ ℓ   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 ) ∈ Q +   with a common center c   if the triangles p ^ q ^ r ^   form a family.
For every μ ∈ N   , let Q μ +   denote the set of high quadruples ( p , q , r , c ) ∈ Q +   such that the triangle p ^ q ^ r ^   on the sphere H c   is part of a family of size at least μ   but less than 2 μ   . Since the size of any family is less than n / 3   , we can partition Q +   into log n   subsets Q + = log n ⋃ j = 0 Q 2 j + .   There is a value μ = 2 j   , 0 ≤ j ≤ log n   , such that | Q μ + | ≥ | Q + | / log n ≥ Ω ( n 2 / log n )   .
Next, we derive an upper bound for the parameter μ   . Each quadruple ( p , q , r , c ) ∈ Q μ +   uniquely determine a family f ( p , q , r , c )   of quadruples of size at least μ   and at most 2 μ   . There are Ω ( n 2 / μ log n )   disjoint quadruple families in Q μ +   . A family f ( p , q , r , c )   corresponds to at least μ   spherical triangles on spheres centered at c   such that their 3 μ   vertices lie on three planes incident to c   . For μ ≥ 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 ∈ 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 λ ⊂ L   denote the set of pairs ( c , F )   such that F   is spanned by at least λ   but less than 2 λ   families in Q μ +   centered at c ∈ P 0   . There is a value λ = 2 k   , 0 ≤ k ≤ log n   , such that the pairs in L λ   correspond to at least Ω ( n 2 / μ log 2 n )   quadruple families of Q μ +   . Since each pair ( c , F ) ∈ L λ   belongs to at least λ   families, the number of point-plane pairs in L λ   is at least | L λ | ≥ Ω ( n 2 / λ μ log 2 n )   .
The pair ( c , F ) ∈ L λ   is an incidence between the point c ∈ P   and a ( λ μ )   -rich plane F   . All incidences are distinct. By Corollary  6 , we have an upper bound on incidences of ( λ μ )   -rich planes in a homogeneous set P   :
Ω ( n 2 λ μ log 2 n ) ≤ | L λ | ≤ O ( n 3 ( λ μ ) 3 ) ,   ( λ μ ) 2 ≤ O ( n log 2 n ) ,  
μ ≤ O ( n ⋅ log n ) . (3)
Q μ +   contains Ω ( n 2 / log n )   quadruples ( p , q , r , c )   where c   is a point from the set P 0   of size Ω ( n )   . There is a set P 1 ⊂ P 0   of size Ω ( n / log n )   such that each c ∈ P 1   is a center of at least Ω ( n / log n )   quadruples of Q μ +   . For every c ∈ P 1   , we define a set of Ω ( n / log n )   triangles in the sphere H c   by T c = { p ^ q ^ r ^ : ( p , q , r , c ) ∈ Q μ + }   For every c ∈ P 1   , let B c   denote the set of m   -rich planes incident to c   . Let 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 p ^ q ^   of a triangle in P ^ ( c )   , the bisector of p ^ q ^   is in B ^ c   .
Consider the simplicial partition of the set P ^ ( c )   for a point c ∈ P 1   . Every set P ^ ( c )   , i = 1 , 2 , … , Θ ( s 2 )   , contains at most O ( t )   triangles of T c   . Since there are Θ ( s 2 ) = Θ ( n / t )   subsets P ^ i ( s )   and | T c | ≤ Ω ( n / log n )   triangles, at least Ω ( s 2 / log n )   subset must contain Ω ( t / log n )   triangles of T c   . For these sets P ^ i ( c )   , the Ω ( t / log n )   triangles determine at least Ω ( ( t / log n μ ) 1 / 3 )   distinct bisectors in B ^ c   . A bisector crosses at most O ( s )   regions, and so we obtain the same bisector of B ^ c   in at most O ( s )   regions. We conclude that the number of bisectors determined by the Ω ( n / log n )   triangles of T c   is
| B c | ≥ Θ ( s 2 / log n ) O ( s ) ⋅ Ω ( ( t / log n μ ) 1 / 3 ) ≥ Ω ( n t ⋅ t 1 / 3 μ 1 / 3 log 4 / 3 n ) ≥
≥ Ω ( n 1 / 2 t 1 / 6 μ 1 / 3 log 4 / 3 n ) .
Using the estimate μ ≤ O ( n ⋅ log n )   from Inequality ( 3 ), we obtain that | B c | ≥ Ω ( n 1 / 3 t 1 / 6 log 5 / 3 n ) .   Each of the Ω ( n / log n )   points of P 1   is incident to Ω ( n 1 / 3 / t 1 / 6 log 5 / 3 n )   distinct m   -rich planes. This gives Ω ( n 4 / 3 / t 1 / 6 log 8 / 3 n )   incidences on m   -rich planes of P   . By Corollary  6 , we have Ω ( n 4 / 3 t 1 / 6 log 8 / 3 n ) ≤ O ( n 3 m 3 ) ,   m 3 ≤ O ( n 5 / 3 t 1 / 6 log 8 / 3 n ) ,  
m ≤ O ( n 5 / 9 t 1 / 18 log 8 / 9 n ) . (4)
Ω ( m 18 n 10 log 16 n ) ≤ t .   In both cases, we have derived lower bounds for t   in terms of n   and m   .
We choose m ∈ N   such that we obtain the same result in both cases. By comparing Inequalities ( 2 ) and ( 4 ), we have Ω ( n 3 / 2 t 3 / 2 ) ≤ m ≤ O ( n 5 / 9 t 1 / 18 log 8 / 9 n ) ,   Ω ( n 17 / 18 log 8 / 9 n ) ≤ t 28 / 18 ,  
Ω ( n 17 / 28 log 4 / 7 n ) ≤ t . (5)
The choice m = ⌊ n 33 / 56 log 12 / 14 n ⌋   establishes Inequality ( 5 ) in both cases.
This completes the proof of Theorem  2  □   References

  1. P. K. Agarwal and B. Aronov, Counting facets and incidences, Discrete Comput. Geom. 7 (1992) 359–369.
  2. B. Aronov, J. Pach, M. Sharir, and G. Tardos, Distinct distances in three and higher dimensions, Combin. Probab. Comput. 13 (2004), 283–293.
  3. B. Aronov and M. Sharir, Cell complexities in hyperplane arrangements, Discrete Comput. Geom. 32 (2004), 107–115.
  4. J. Beck, On the lattice property of the plane and some problems of Dirac, Motzkin and Erdős, Combinatorica 3 (3-4) (1983), 281–297.
  5. B. Chazelle. The Discrepancy Method. Cambridge University Press, 2000.
  6. 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.
  7. 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, Springer-Verlag, Berlin, 1990, pp. 419–428.
  8. Gy. Elekes, A note on the number of distinct distances, Period. Math. Hungar. 38 (1999), 173–177.
  9. Gy. Elekes and Cs. D. Tóth, Incidences of not-too-degenerate hyperplanes, in Proc. 21st ACM Sympos. Comput. Geom. (Pisa, 2005), ACM Press, to appear.
  10. P. Erdős, On sets of distances of n   points, Amer. Math. Monthly 53 (1946), 248–250.
  11. S. Hofmann and A. Iosevich, Circular averages and Falconer-Erdős distance conjecture in the plane for random metrics, Proc. Amer. Math. Soc. 133 (1) (2005), 133–143
  12. A. Iosevich, Curvature, combinatorics, and the Fourier transform, Notices Amer. Math. Soc. 48 (2001), 577–583.
  13. A. Iosevich, N. Katz, and S. Pedersen, Fourier basis and the Erdős distance problem, Math. Research Letters 6 (2) (1999), 251–255.
  14. A. Iosevich and I. Łaba, Distance sets of well-distributed planar point sets, Discrete Comput. Geom. 31 (2004), 243–250.
  15. S. Konyagin and I. Łaba, Distance sets of well-distributed planar sets for polygonal norms, Israel J. Math. to appear.
  16. 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.
  17. J. Matoušek, Efficient partition trees, Discrete Comput. Geom. 8 (1992), 315–334.
  18. 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.
  19. J. Solymosi, G. Tardos, and Cs. D. Tóth, The k   most frequent distances in the plane, Discrete Comput. Geom. 28 (2002), 639–648.
  20. J. Solymosi and Cs. D. Tóth, Distinct distances in the plane, Discrete Comput. Geom. 25 (2001), 629–634.
  21. 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.
  22. J. Solymosi and V. Vu, Near optimal bounds for the Erdős distinct distance problem in high dimensions, Combinatorica to appear.
  23. E. Szemerédi and W. T. Trotter Jr., Extremal problems in Discrete Geometry, Combinatorica 3 (3–4) (1983), 381–392.
  24. L. A. Székely, Crossing numbers and hard Erdős problems in discrete geometry, Combinatorics, Probability & Computing 6 (3) (1997), 353–358.