Distinct Distances in Three and Higher Dimensions?
Boris Aronov? J?nos Pach? a Micha Sharir§ G?bor Tardos? a
ABSTRACT
Improving an old result of Clarkson et al., we show that the number of distinct distances determined by a set P of n points in three-dimensional space is ?(n77/141?ε ) = ?(n0.546 ), for any ε > 0. Moreover, there always exists a point p ∈ P from which there are at least these many distinct distances to the remaining elements of P . The same result holds for points on the three-dimensional sphere. As a consequence, we obtain analogous results in higher dimensions.
General Terms
Theory
Keywords
Distinct distances, Incidences, Point con?gurations
1.
Introduction
Categories and Subject Descriptors
F.2.2 [Theory of Computation]: Nonnumerical Algorithms and Problems—geometrical problems and computations
? Work on this paper by the ?rst three authors has been supported by a grant from the U.S.-Israeli Binational Science Foundation. Work by Boris Aronov has also been supported by NSF Grants CCR-99-72568 and ITR CCR-00-81964. Work by J?nos Pach and a Micha Sharir has also been supported by NSF Grants CCR-9732101 and CCR-00-98246. Work by J?nos Pach has also been a supported by a PSC-CUNY Award, and work by Micha Sharir by a grant from the Israel Science Fund (for a Center of Excellence in Geometric Computing) and by the Hermann Minkowski– MINERVA Center for Geometry at Tel Aviv University. Work by G?bor Tardos has been supported by Hungarian Science Foundaa tion grants OTKA T029255, OTKA T030059, and AKP 2000-78 2.1. ?Department of Computer and Information Science, Polytechnic University, Brooklyn, NY 11201-3840, USA; aronov@poly.edu. ?City College, CUNY, and Courant Institute of Mathematical Sciences, New York University, New York, NY 10012, USA; pach@cims.nyu.edu. § School of Computer Science, Tel Aviv University, Tel Aviv 69978 Israel and Courant Institute of Mathematical Sciences, New York University, New York, NY 10012, USA; michas@post.tau.ac.il. Part of the work on this paper was performed when Micha Sharir visited ETH Z¨rich in the spring of 2001. u ?R?nyi Institute, Hungarian Academy of Sciences, Pf. 127, He 1354 Budapest, Hungary; tardos@renyi.hu.
“My most striking contribution to geometry is, no doubt, my problem on the number of distinct distances”—wrote Erd?s on his 80th birthday [8]. What is the minimum numo ber of distinct interpoint distances determined by n points in Rd ? More precisely, Erd?s [7] asked the following question o in 1946. Given a point set P , let g(P ) denote the number of distinct distances between the elements of P . Let gd (n) = minP g(P ), where the minimum is taken over all sets P of n distinct points in d-space. We want to describe the asymptotic behavior of the function gd (n). More than 50 years later, in spite of considerable e?orts, we are still far from knowing the correct order of magnitude of gd (n) even in the plane (d = 2). This problem is more than just a “gem” in recreational mathematics. It was an important motivating trigger, along with several companion problems, such as those of repeated distances and of point-curve incidences, that have led to the discovery of important new concepts and methods (levels in arrangements, space decompositions, cuttings, epsilon-net techniques, etc.) which proved to be relevant in many areas of discrete and computational geometry, including motion planning and ray shooting. Erd?s’ question is intimately related to another problem o raised in the same paper: what is the maximum number of times that the same distance can occur among n points in d-space? Denoting this function by fd (n), we clearly have, by the pigeonhole principle, that gd (n) ≥
n 2
fd (n)
.
(1)
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for pro?t or commercial advantage and that copies bear this notice and the full citation on the ?rst page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior speci?c permission and/or a fee. STOC’03, June 9–11, 2003, San Diego, California, USA. Copyright 2003 ACM 1-58113-674-9/03/0006 ...$5.00.
Spencer et al. [15] and Clarkson et al. [4], respectively, proved that f2 (n) = O(n4/3 ) and f3 (n) = O(n3/2 β(n)), where 2 β(n) = 2O(α (n)) and α(n) is the extremely slowly growing inverse Ackermann’s function. Therefore, we have g2 (n) = ?(n2/3 ), g3 (n) = ?(n1/2 /β(n)). (2)
Because small multiplicative factors such as β(n) often appear in our calculations, we introduce the notation f (n) = O(g(n)) to denote f (n) = O(g(n)nε ), for any ε > 0, with
the implied constant depending on ε. Similarly, f (n) = ?(g(n)) means that f (n) = ?(g(n)n?ε ), for any ε > 0. With this notation, a single distance occurs at most O(n3/2 ) times among n points in three dimensions, and thus g3 (n) = ?(n1/2 ). For d ≥ 4, the above “naive” approach based on (1) cannot give any nontrivial lower bound on the number gd (n) of distinct distances determined by n points, because we have fd (n) ≥ n2 /4. To see that a single distance can appear n2 /4 times, consider two circles centered at the origin, whose planes are orthogonal to each other, and place n/2 points on each of them. Observe that all distances between a point on one of the circles and a point on the other are the same. The ?rst bound in (2) has been subsequently improved by Chung et al. [3], Sz?kely [16], Solymosi and T?th [13], Tardos e o [18], Katz [9], and Katz and Tardos [10] culminating in the lower bound g2 (n) = ?(n(48?14e)/(55?19e) ) = ?(n0.86413 ). On the other hand, the best known upper bound, which is due to Erd?s and is conjectured to be sharp, is g2 (n) = o √ O(n/ log n). It is attained by the set of vertices of the n1/2 × n1/2 integer lattice. In three dimensions, however, nothing better was known than the “naive” bound in (2). The aim of this paper is to present such an improvement. Speci?cally, we have Theorem 1.1. A set P of n points in three dimensions determines at least ? n77/141 = ? n0.546 distinct distances. Moreover, there always exists a point p ∈ P that determines at least these many distinct distances to the remaining points of P . The number of distinct distances determined by the vertices of an n1/3 × n1/3 × n1/3 integer lattice is Θ(n2/3 ). That is, we have g3 (n) = O(n2/3 ), and it is conjectured that this bound is not far from being sharp. For more problems and results of this type, consult [12]. Let tp (P ) stand for the number of distinct distances between a point p and the elements of P \ {p}, and put t(P ) = maxp∈P tp (P ). Finally, let t3 (n) = min t(P ), where the minimum is taken over all n-element point sets P in R3 . Clearly, t(P ) ≤ g(P ) and our result can be stated as g3 (n) ≥ t3 (n) = ? n77/141 = ?(n0.546 ). As in most of all the earlier approaches to the planar problem [3, 4], our proof establishes an upper bound for the number I(P, S) of incidences between the points in P and the set S of all spheres around the elements of P , passing through at least one other point of P . Clearly, the number of these spheres is at most nt(P ). Since I(P, S) is n(n ? 1), this leads to an inequality for t(P ), whose solution yields a lower bound for t(P ). The most serious technical di?culty in the proof of our main result is that in three dimensions we may encounter ‘large’ con?gurations, each involving many points of P lying on a circle and many other points of P lying on the line orthogonal to the circle and passing through its center (the ‘axis’ of the circle). See Figure 1. This leads to a complete bipartite pattern of incidences between the set of points on
the circle and the set of spheres centered at the points on the axis and passing through the circle. Such con?gurations hinder the derivation of a sharp bound for I(P, S), so we start the proof by removing all points of P that lie on lines containing too many points.
Figure 1: A complete bipartite incidence pattern. We also extend the results of Theorem 1.1 to point sets in the three-dimensional unit sphere S3 ? R4 : Theorem 1.2. A set P of n points in S3 determines at least ? n77/141 = ? n0.546 distinct distances. Moreover, there always exists a point p ∈ P that determines at least these many distances to the remaining points of P . The spherical result readily generalizes to distances in higher dimensions: Corollary 1.3. For d ≥ 3, any set P of n points in Euclidean d-space Rd or on the d-sphere Sd determines at least ? n1/(d? 77 ) distinct distances. Moreover, there always exists a point p ∈ P that determines at least these many distances to the remaining points of P . As for d = 3, the number of distinct distances determined by an n1/d × · · · × n1/d portion of the integer lattice is O(n2/d ), so that we have gd (n) = O(n2/d ). The next three sections are devoted to the proof of Theorem 1.1. We prove Theorem 1.2 and Corollary 1.3 in Section 5. In Section 6 we make a few concluding remarks. We need the following two results. Theorem A ([17, 4, 16]). The number of incidences between n points and m pseudo-segments (i.e., Jordan arcs, any two of which have at most one point in common) is O(n2/3 m2/3 + n + m). Theorem B ([1]). The number of incidences between n points and m circles in Rd is O(n6/11 m9/11 + n2/3 m2/3 + n + m).
90
2.
Lines with Many Points
Let P be a set of n points in R3 . Let t = t(P ) and recall that our ?nal goal is to prove a lower bound on t. As mentioned in the introduction, we have to pay special attention to the lines containing many points of P . In this section we establish a reasonably small threshold ?0 so that only a negligibly small number of points of P lie on lines that contain more than ?0 points. No line ? contains more than t + 1 points of P , since the distance from an extremal point of ? ∩ P to all other points of ? ∩ P on the line are distinct. For any line ?, let ?? = |? ∩ P | and let C? be the set of circles having ? as an axis and containing at least one point of P . Our goal is to bound the size |C? | of this set. Consider the set S? of all the spheres centered at points of ? ∩ P and containing at least one point of P . We ?x a halfplane O bounded by ?. Each sphere in S? intersects O in a semicircle, and each circle in C? intersects O at a single point. Moreover, the intersection semicircles are distinct for distinct spheres of S? , and the intersection points are distinct for distinct circles of C? . See Figure 2. Since every circle γ ∈ C? is contained in exactly ?? of the spheres of S? , we have |C? |?? incidences between the at most ?? t semicircles and the |C? | points within O. Clearly, these semicircles form a collection of pseudo-segments, that is, each pair of them intersects at most once. Hence, Theorem A implies that |C? |?? = O (|C? |?? t)2/3 + ?? t + |C? | . (3)
We now consider the collection L? of all lines ? with ?? ≥ ? for some parameter ? > a. Let C? be the union of the sets C? , for ? ∈ L? . Notice that the sets C? are disjoint for distinct lines ?. We count the number of incidences between the points in P and the circles in C? . Each collection C? contributes n ? ?? such incidences. We may assume that n ? ?? ≥ n/2, as otherwise t = ?(n). Thus, we have at least n|L? |/2 incidences between the n points of P and the O(|L? |t2 /?) circles of C? . Using Theorem B on circle-point incidences in three dimensions, we obtain n|L? |/2 = O(n6/11 (|L? |t2 /?)9/11
+ n2/3 (|L? |t2 /?)2/3 + n + |L? |t2 /?). t4 t9 + 9/2 5/2 2n ? ? n
(4)
Solving (4) for |L? |, it follows that either ? = O(t2 /n) or |L? | = O 1 + . (5)
Let us choose ?0 such that (5) holds for all ? ≥ ?0 . Let X be the set of points in P incident to at least one line in L?0 . Clearly, |X| ≤
i≥0
2i+1 ?0 |L2i ?0 |.
Notice that L2i ?0 = ? if 2i ?0 > t + 1. Hence |X| = O t + t9 t4 + 7/2 ?0 n ?0 n5/2 .
By the de?nition of O, this can be rephrased as
p q c1 c2
|X| ≤
t+
t4 t9 + 7/2 ?0 n ?0 n5/2
γ(n),
where we may take γ(n) to satisfy log n < γ(n) = O(1). We choose the value ?0 = γ 2 (n)t18/7 /n = O(t18/7 /n). The above bound yields |X| = o(n) unless t > n0.7 . In the latter case, there is nothing to prove, as our ?nal goal is a much weaker lower bound on t. The following lemma summarizes our results so far. Lemma 2.1. Let P be a set of n distinct points in R3 and let t = t(P ). If t ≤ n0.7 we can set ?0 = O(t18/7 /n) such that the total number of points in P incident to lines containing at least ?0 points of P is only o(n).
O
Figure 2: Circle-sphere containments along a ?xed axis. The two points p, q on the axis and the two circles c1 , c2 (shown projected orthogonally to O) induce four spheres, each centered at one of the points and containing one of the circles. Each circle-sphere containment is mapped into an incidence between a point and a semicircle. Rewriting (3), we deduce that one of the inequalities ?? ≤ a, |C? | ≤ at, or |C? | ≤ at2 /?? must hold, for some absolute constant a. Using the fact that ?? ≤ t + 1, we have at = O(t2 /?? ). Hence, we have |C? | = O whenever ?? > a. t2 ?? ,
3.
Incidences with Good Spheres
Let P be a set of n points in R3 . We classify each (twodimensional) sphere σ as being either good with respect to P , if no circle that lies fully in σ contains more than half of the points in σ ∩ P , or bad, otherwise. In this section, we bound the number of incidences between a set of good spheres and P . Let G be a ?nite set of good spheres. Lemma 3.1. The number of incidences between P and G is O(n|G|3/4 ). Proof. Consider the following set of quintuples: Q = {(p1 , p2 , p3 , p4 , σ) | σ ∈ G, p1 , p2 , p3 , p4 distinct non-coplanar points of P ∩ σ}.
We clearly have |Q| ≤ n4 , since any quadruple {p1 , p2 , p3 , p4 } of non-coplanar points determine at most one sphere of G that contains them all. To obtain a lower bound on |Q|, we ?x a sphere σ ∈ G and put nσ = |P ∩ σ|. Notice that, as σ is good, we have nσ ≥ 6. We construct the quintuples in Q involving σ by selecting the points p1 , p2 , p3 , and p4 one by one. Clearly, p1 can be chosen in nσ di?erent ways, while 2 we have nσ ? 1 ≥ 5 nσ choices for p2 and nσ ? 2 ≥ 3 nσ 6 choices for p3 . After p1 , p2 , and p3 have been selected, p4 must be chosen in σ ∩ P but o? the circle determined by the ?rst three points. Since σ is good, we have at least nσ /2 choices for p4 . We thus obtain the following lower bound on the size of Q: |Q| ≥ 5 ( 5 4 nσ ≥ 18 18 σ∈G
σ∈G nσ ) |G|3 4
It remains to bound the number of incidences between points in a cell and spheres crossing it. For any cell τ , put Pτ ≡ P ∩τ , let Sτ denote the set of the at most nt/r spheres of S that cross τ , and let Gτ (resp., Bτ ) denote the subset of good (resp., bad) spheres of Sτ , with respect to Pτ . By Lemma 3.1, the number of incidences between Pτ and Gτ is O(|Pτ | · |Gτ |3/4 ). Summing this bound over all cells τ , we obtain a contribution of O(|Pτ | · |Gτ |3/4 ) = O n =O nt r
3/4
τ
n7/4 t3/4 r 3/4
(6)
.
Comparing this with the n4 upper bound on the same quantity, we get the asserted upper bound on the number σ∈G nσ of incidences between points in P and spheres in G.
4.
Decomposition
In this section, we complete the proof of Theorem 1.1. First we use Lemma 2.1 to eliminate all points of P that lie on lines containing many points, and then we combine Lemma 3.1 with a standard random sampling argument, to obtain the desired lower bound on t(P ). We are given a set P of n points in R3 . Let t = t(P ). If t > n0.7 we are done. Otherwise we choose ?0 = O(t18/7 /n) so that Lemma 2.1 holds. Using the lemma, we may assume, without loss of generality, that no line contains ?0 or more points from P . Indeed, since t ≤ n0.7 , we simply remove from P those o(n) points that lie on lines containing at least ?0 points, and apply the argument to the remaining set. Consider the set S of spheres centered at the points of P , each containing at least one element of P . Clearly, we have |S| ≤ nt. We ?x a parameter r, whose value will be determined below, and construct a (1/r)-cutting of S. Using an extension of the method of Chazelle and Friedman [2], reviewed in [11], which is based on the vertical decomposition technique presented in [4], we obtain a cutting consisting of O(r 3 ) connected, relatively open cells of dimension 0, 1, 2, or 3, so that each cell is crossed by (i.e., intersected by, but not fully contained in) at most nt/r spheres in S. We ?rst bound the number of incidences involving points that lie in some cell and spheres that fully contain that cell. Consider a ?xed cell τ . If τ is 0-dimensional, i.e., a single point, it contributes at most n incidences, for a total of O(nr 3 ). If τ is 2-dimensional, it can be fully contained in at most one sphere of S, and these full containments produce at most n incidences in total, because each point of P lies in at most one such cell. If τ is 3-dimensional, no sphere can fully contain it. If τ is 1-dimensional, the only nontrivial case is when τ is a circular arc contained in several spheres. However, the maximum number of such spheres is at most ?0 , because the centers of all these spheres lie on the axis of the circle containing τ . Hence, the number of incidences produced by the full containments by 1-dimensional cells is at most O(n?0 ) (again, each point lies in at most one 1dimensional cell). In summary, full containments generate O(n?0 + nr 3 ) incidences.
incidences. We next estimate the contribution of bad spheres to the number of incidences. Fix a cell τ . For each bad sphere σ ∈ Bτ , we can just consider the more than |σ ∩Pτ |/2 points that lie on a common circle γ along σ. We choose one such circle γ = γ(σ, τ ), and we lose at most half the incidences between Pτ and σ in doing so. In other words, we have constructed a set Cτ of circles, where each circle γ ∈ Cτ appears with some multiplicity ?γ,τ , which is the number of bad spheres σ ∈ Bτ that satisfy γ(σ, τ ) = γ. We wish to bound the number of incidences between the points of Pτ and the circles of Cτ , where each such incidence is to be counted with the multiplicity of the corresponding circle. Namely, we wish to bound the sum
τ γ∈Cτ
?γ,τ |γ ∩ Pτ | .
(?)
Fix a parameter ? > 0, consider the subset Cτ of circles in Cτ with multiplicity between ? and 2?. We have (?) (?) ?|Cτ | ≤ |Sτ | ≤ nt/r, so that Nτ ≡ |Cτ | ≤ nt/(r?). By Theorem B the number of incidences between Nτ distinct circles and nτ ≡ |Pτ | points in 3-space is
2/3 6/11 9/11 + n2/3 Nτ + nτ + Nτ . O nτ Nτ τ
We multiply this bound by 2?, the bound on the multiplicity (?) of any circle in Cτ , and sum it over all cells τ , to obtain that the total number of incidences between the points of P in a cell τ and the bad spheres whose representing circles (?) are in the subset Cτ , summed over all cells τ , is O ?
τ
n6/11 τ ?
τ
nt r? nt r?
9/11
+
2/3
n2/3 τ
+?
τ
nτ + nt r?
2/3 9/11
nt r?
= O ?n6/11 (r 3 )5/11 + ?n2/3 (r 3 )1/3 nt r?
+ n? + ntr 2
(7)
= O(n15/11 t9/11 r 6/11 ?2/11 + n4/3 t2/3 r 1/3 ?1/3 + n? + ntr 2 ). If a circle γ appears in Cτ with multiplicity ?, then there are ? spheres whose centers all lie on the axis of γ. By our
initial pruning process, we have ? ≤ ?0 . We can therefore bound the number of all “bad” incidences by summing (7) over an appropriate geometric progression of ? ending at ?0 = O(t18/7 /n), and then combine the sum with the bound (6) on “good” incidences and with the bounds for incidences between points in a cell and spheres containing the entire cell, to obtain (the ?fth term has an additional logarithmic factor, which is subsumed by the factor implied by the O-notation) n(n ? 1) = I(P, S) = O( n7/4 t3/4 + n13/11 t9/7 r 6/11 + r 3/4 nt32/21 r 1/3 + t18/7 + ntr 2 + nr 3 ).
We choose r = n25/57 /t55/133 > 1 to equalize the ?rst two terms on the right-hand side, obtaining n2 = O n27/19 t141/133 + n196/171 t79/57 + t18/7 + n107/57 t23/133 + n132/57 /t165/133 . Solving this inequality for t yields that one of the following ?ve relations must hold: t = ? n77/141 , t = ? n7/9 , or t = O n14/55 . Here the last relation is impossible, as we already know that t = ?(n1/2 ). From the ?rst four relations the weakest one— the ?rst—is the bound claimed in Theorem 1.1. 2 t = ? n146/237 , t = ? n49/69 ,
5.
Distinct Distances in Sd and Rd
We leave S3 and consider the Euclidean 4-space R4 containing it. Let O be the (two-dimensional) plane in R4 containing the great circle ?. We project the spheres in S? and the circles in C? orthogonally onto O. Any sphere in S? is in fact the intersection of two spheres in R4 , one of which is the unit sphere S3 containing ?, and the other is a sphere centered at a point of ?. The projection of this intersection is a chord of ?. Note also that distinct spheres project to distinct chords. The circles in C? are contained in planes orthogonal to O, so each of them projects to a single point of O (inside the circle ?). Here again, distinct circles in C? project to distinct points. Each circle in C? lies in ?? spheres in S? , creating at least |C? |?? incidences between the points and the chords in the projection. Thus, by Theorem A, the bound (3) also holds in this case. The rest of the proof of Theorem 1.1 applies essentially verbatim in this case. Notice that for the Euclidean case one has to use Theorem B on point-circle incidences in three dimensions, whereas to derive the same bound (4) in the spherical case we use the result in four dimensions. The portion of the proof in Section 3 proceeds without any change. For the ?nal part in Section 4, one has to use (1/r)-cuttings within S3 , whose existence and properties can be established following the approach mentioned in Section 4. Finally, we prove Corollary 1.3. The proof proceeds by induction on d. The base case d = 3 is covered by Theorems 1.1 and 1.2. For d > 3, ?x an arbitrary point p ∈ P . There are tp (P ) (d ? 1)-dimensional spheres centered at p that collectively contain the n ? 1 points of P \ {p}. Hence, there is a sphere σ passing through at least (n ? 1)/tp (P ) elements of P . If tp (P ) is smaller than the asserted bound, 90 then σ contains more than n1?1/(d? 77 ) points of P . By the induction hypothesis, we may apply Corollary 1.3 to σ ∩ P , and conclude that there exists a point q ∈ σ ∩ P that determines at least ? n1?1/(d? 77 )
90
We start with proving Theorem 1.2. We only point out the few places where the proof of Theorem 1.1 has to be altered to apply to the spherical case. First, the axis of a circle (the locus of points from which every point of the circle is equidistant) is a great circle in S3 . Thus, we need to modify the analysis so that it handles axes that are great circles, rather than lines. Second, it is su?cient to prove our lower bound for point sets contained in an open hemisphere of S3 . This assumption has two advantages. In R3 , the axis of a circle cannot contain more than t+1 points. This remains true on a hemisphere (within which the axis is a great semi-circle), but a full great circle could contain as many as 2t + 1 distinct points. A more important consequence of this assumption is that when we consider spheres centered at points of our set, no sphere arises more than once. In the full S3 , spheres around diagonally opposite points could coincide. The only subsequent place in the proof where the analysis of the spherical and the Euclidean cases di?er is in the proof of the bound (3) in Section 2. We recall the setting: P is set of n points, now in a hemisphere of S3 . We let t = t(P ). We pick a great circle ? that contains ?? points of P . We de?ne C? to be the set of circles, each having ? as an axis and containing at least one point of P . Our goal is to bound |C? | using the bound (3), restated here: |C? |?? = O (|C? |?? t)2/3 + ?? t + |C? | . (3)
1/(d?1? 90 ) 77
= ? n1/(d? 77 )
90
distinct distances to the other points of σ ∩ P , completing the proof of Corollary 1.3.
6.
Discussion
Clearly, the main open problem is to improve the bound obtained in this paper, to a bound close to ?(n2/3 ). For this, other approaches should also be considered, for example, variants of those used by Sz?kely [16] and by Solymosi and e T?th [13] for the planar case. o We note that an earlier draft of this paper used results of Elekes [5, 6] on the number of distinct distances determined by two sets of points, each consisting of ? points on a line. If the lines are neither parallel nor orthogonal, then there are ?(?5/4 ) distinct distances between the two sets. This result was applied to points lying on axes of the circles that contain points of P . In the present analysis, however, the bottleneck is the case where the axes of circles contain approximately ? ≈ (n77/141 )18/7 /n = n19/47 points of P and ?5/4 < n77/141 , thus Elekes’ result cannot be used to improve the analysis. Elekes’ bound, however, is conjectured (e.g., by Elekes himself) not to be tight, and a major improvement of it would lead to a stronger lower bound on g3 (n) (but not on the number t3 (n) of distinct distances from a single point).
Another improvement would result if one could further improve the bound of Theorem B of [1] for the number of incidences between points and circles in three and four dimensions. This indeed can be done for point sets with certain special properties. For example, for so-called dense sets P , for which the ratio between the maximum and minimum distances between their elements is O(n1/3 ), one can improve the bound on the number of incidences between arbitrary circles and the points in P . This, in turn, yields an improvement on the number of distinct distances for such sets. A recent work by Solymosi and Vu [14] pushes the bound further for this special case, showing that for dense sets of n points in 3-space one has ?(n5/9 ) distinct distances. We conjecture that our bound on g3 (n) is far from being sharp and that the best bound is close to ?(n2/3 ). As a ?rst challenge, which we believe not to be too di?cult, we pose the problem of showing that g3 (n) = ?(n5/9 ). Even with the improvements that one might hope to achieve, as discussed above, the current approach does not extend to proving a bound beyond ?(n5/9 ). This can be seen by considering only the two terms O n7/4 t3/4 + ntr 2 , r 3/4
where the ?rst term bounds the number of incidences with good spheres, and the second bounds incidences involving spheres that cross cells of the cutting but meet there only O(1) points. Choosing r to balance the two terms and solving the resulting inequality for t, we would have obtained t = ?(n5/9 ).
Acknowledgments
We would like to thank Pankaj K. Agarwal for helpful discussions concerning this problem.
References
[1] B. Aronov, V. Koltun and M. Sharir, Incidences between points and circles in three and higher dimensions, Discrete Comput. Geom., submitted. (An earlier version appeared in Proc. 18th ACM Symp. on Computational Geometry (2002), 116–122.)
[2] B. Chazelle and J. Friedman, A deterministic view of random sampling and its use in geometry, Combinatorica 10 (1990), 229–249. [3] F. Chung, E. Szemer?di, and W. T. Trotter, The number e of distinct distances determined by a set of points in the Euclidean plane, Discrete Comput. Geom. 7 (1992), 1–11. [4] K. Clarkson, H. Edelsbrunner, L. Guibas, M. Sharir and E. Welzl, Combinatorial complexity bounds for arrangements of curves and spheres, Discrete Comput. Geom. 5 (1990), 99–160. [5] G. Elekes, A note on the number of distinct distances, Periodica Math. Hung. 38(3) (1999), 173–177. [6] G. Elekes, Sums versus products in number theory, algebra and Erd?s geometry, manuscript, 2001. o [7] P. Erd?s, On sets of distances of n points, Amer. Math. o Monthly 53 (1946), 248–250. [8] P. Erd?s, On some of my favourite theorems, in: Como binatorics, Paul Erd?s is Eighty, Vol. 2 (D. Mikl?s et al., o o eds.), Bolyai Society Mathematical Studies 2, Budapest, 1996, 97-132. [9] N. H. Katz, An improvement of a lemma of Tardos, unpublished. [10] N. H. Katz and G. Tardos, Note on distinct sums and distinct distances, unpublished. [11] J. Matouˇek, Lectures on Discrete Geometry, GTM Ses ries, Springer Verlag, New York, 2002. [12] J. Pach and P.K. Agarwal, Combinatorial Geometry, Wiley, New York, 1995. [13] J. Solymosi and Cs. T?th, Distinct distances in the o plane, Discrete Comput. Geom. 25 (2001), 629–634. [14] J. Solymosi and V. Vu, Distinct distances in homogeneous pointsets, to appear in Proc. 19th ACM Sympos. Comput. Geom., 2003. [15] J. Spencer, E. Szemer?di, and W. T. Trotter, Unit dise tances in the Euclidean plane, in: Graph Theory and Combinatorics (B. Bollob?s, ed.), Academic Press, New a York, 1984, 293–303. [16] L. Sz?kely, Crossing numbers and hard Erd?s probe o lems in discrete geometry, Combinatorics, Probability and Computing 6 (1997), 353–358. [17] E. Szemer?di and W. T. Trotter, Extremal problems in e discrete geometry, Combinatorica 3 (1983), 381–392. [18] G. Tardos, On distinct sums and distinct distances, Advances in Mathematics, to appear.