# Distinct distances from three points

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

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$.

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})$.

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.

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.)

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.