Distinct distances from three points

This post is about the recent paper of Sharir and Solymosi concerning distinct distances from three points.

michasSolymosi

Let {\cal P}_1  and {\cal P}_2  be two sets of points in the plane, and let D({\cal P}_1,{\cal P}_2)  denote the number of distinct distances that are determined by a point of {\cal P}_1  and a point of {\cal P}_2  . The case where the points of each set are on a distinct line was considered in this paper by Sharir, Solymosi, and myself, and a generalization to the case where the points are on two general constant-degree curves was recently derived by Pach and de Zeeuw. Instead of restricting the point sets to curves, we now consider the case where {\cal P}_1  contains only a constant number of points (and |{\cal P}_2|=n  ).

If {\cal P}_1  contains a single point p  , then by putting the points of {\cal P}_2  on a common circle around p  , we obtain D({\cal P}_1,{\cal P}_2) = 1  .

OneCenter

Next, consider the case where {\cal P}_1  contains two points p,q  . Let D=\{d_1,d_2,\ldots\}  be the set of distinct distances between points of {\cal P}_1  and points of {\cal P}_2  . Consider the |D|  circles that are centered around p  and have a radius from D  , and the |D|  circles that are centered around q  that have a radius from D  . Since D  consists of all the distances between {\cal P}_1  and {\cal P}_2  , every point of {\cal P}_1  must be contained in an intersection of two circles. Let r  be the distance between p  and q  and let D=\{d_1,d_2,\ldots\}  be a set of \sqrt{n}  distinct distances, all larger than r  and smaller than 2r  . In this case, the two sets of circles intersect in exactly 2n  points. We can arbitrarily choose n  of these intersection points to be the points {\cal P}_2  . This implies that when |{\cal P}_1|=2  it is possible to have D({\cal P}_1,{\cal P}_2) = O(\sqrt{n})  .

TwoCenters

To see that this bound is tight, assume for contradition that D({\cal P}_1,{\cal P}_2) = o(\sqrt{n})  and notice that there are o(n)  intersection points between the two sets of circles, which makes it impossible for the n  points of {\cal P}_2  to be intersection points. A nice corollary of this is that for every set \cal P  of n  points in the plane, there exists at most one point p\in{\cal P}  such that p  determines o(\sqrt{n})  distinct distinct distances with the points of {\cal P}\setminus\{p\}  .

The case where {\cal P}_1  contains three points p_1,p_2,p_3  is the first non-trivial case. As before, we can equivalently consider three families of circles, each centered around a different p_i  , and find an upper bound for the number of points that are contained in three circles.

ThreeCircles

While some version of this problem was mentioned in a paper by Erdös, Lovász, and Vesztergombi, the first breakthrough was obtained by Elekes, who constructed a configuarion where the three points p_1,p_2,p_3  are collinear and D({\cal P}_1,{\cal P}_2) = O(\sqrt{m})  . In fact, this construction works for any constant number of collinear points. (The following figure is taken from the book “Research Problems in discrete Geometry” by Brass, Moser, and Pach.)

CircleGrid

Many years later, Elekes and Szabó proved that if the three points p_1,p_2,p_3  are not collinear, then D({\cal P}_1,{\cal P}_2) = \Omega(n^{0.502})  . This discovery made it started to seem likely that when p_1,p_2,p_3  are not collinear, then value of D({\cal P}_1,{\cal P}_2)  should be siginificantly larger, and perhaps even \Theta(n)  . The new paper of Sharir and Solymosi, improves the bound of Elekes and Szabó, and proves that if p_1,p_2,p_3  are not collinear, then D({\cal P}_1,{\cal P}_2) = \Omega(n^{6/11}  ). As before, this yields a nice corollary: For every set \cal P  of n  points in the plane, there exists a line \ell  such that every point p\in{\cal P} \setminus \ell  determines \Omega(n^{6/11})  distinct distances with the points of {\cal P}\setminus\{p\}  .

To derive this new bound, Sharir and Solymosi relied on the same framework as in their recent paper with me, and as in the recent paper of Pach and de Zeeuw. I am tempted to start referring to this framework as the partial Elekes-Sharir framework since it relies on some of the ideas of the Elekes-Sharir framework but ignores others. Just as in the Elekes-Sharir framework, the partial framework is based on double counting the size of a set Q  of quadruples of some sort, and obtains a lower bound on |Q|  by a simple use of the Cauchy–Schwarz inequality. However, while the Elekes-Sharir framework reduces the problem of obtaining an upper bound for |Q|  to bounding the number of intersections of lines in {\mathbb R}^3  , the partial framework reduces the problem to a planar point-curve incidence problem. (See my guide to the Elekes-Sharir framework here.)

Sharir and Solymosi’s use of the partial framework is somewhat unusual since the elements of Q  are not quadruples of points, but rather quadruples of distances. However, since this post is not intended to be a technical one, I will not give more details and stop here.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s