Distinct Distances: Open Problems and Current Bounds

If you have been following this blog for a while, you might have noticed that I have been slowly surveying the various open problems that are related to distinct distances, and the best known bounds for them. I think that my survey is now in a decent shape, so I uploaded it on arXiv.

For this occasion, I wish to mention an open problem concerning surfaces in {\mathbb R}^3  . It is far from being one of the main problems of this subfield. However, since currently no non-trivial bounds are known for it, it seems like a good problem for a student or for someone who wishes to start working on distinct distances problems.

Recall that in bipartite distinct distances problems we have two sets of points {\cal P}_1  and {\cal P}_2  , and are interested only in distinct distances that are spanned by pairs of {\cal P}_1\times{\cal P}_2  (i.e., distances between points from different sets). For simplicity, in this post we assume that both sets are of cardinality n  . One example of such a result, by Pach and de Zeeuw, is that if each of the two point sets is on a planar curve that contains no lines or circles, then the number of distinct distances between {\cal P}_1  and {\cal P}_2  is \Omega\left(n^{4/3}\right).

In {\mathbb R}^d  , the similar (yet non-bipartite) case where one point set is placed a curve was studied by Charalambides and by Raz, Sharir, and Solymosi. However, nothing non-trivial is known for point sets on two-dimensional surfaces. That is, consider, in {\mathbb R}^3  , the minimum number of distinct distances between a set {\cal P}_1  of n  points on a two-dimensional surface S_1  , and a set {\cal P}_2  of n  points on a two-dimensional surface S_2  .

Before we properly formulate any questions for this scenario, let us first consider some examples. First, consider the case where S_1  and S_2  are non-parallel planes in {\mathbb R}^3  . In this case there exist two orthogonal lines \ell_1,\ell_2  such that \ell_1 \subset S_1  , \ell_2 \subset S_2  , and \ell_1 \cap \ell_2  is a point on S_1 \cap S_2  . We can place the two sets of points on \ell_1,\ell_2  such that the number of distinct distances between the two sets is \Theta(n)  (e.g., see Section 3 of the survey). The same bound can be obtained between two spheres and between a sphere and a plane (in both cases by placing the points on two parallel circles).

A slightly better bound can be obtained in the case where S_1  and S_2  are parallel planes. In this case we can place a \sqrt{n}\times\sqrt{n} subset of the integer lattice on each of the planes. For example, we may assume that the planes are defined by z=0  and z=1  , and that the points of the two sets are

{\cal P}_1 \cup {\cal P}_2 = \left\{ (x,y,z) | 1 \le x,y \le \sqrt{n} \quad \text{ and } \quad 1 \le z \le 2 \right\}.

A variant of Erdős’ analysis of the planar lattice (e.g., see Section 2 of the survey) implies that the number of distinct distances between the two sets is O(n/\sqrt{\log n})  .

Unlike the planar case, it is not immediately clear whether the above examples are tight. For example, the n^{1/3}\times n^{1/3} \times n^{1/3}  integer lattice determines only O\left(n^{2/3}\right)  distinct distances. This leads to the following conjecture.

Conjecture. Given a set {\cal P}_1  of n  points on a two-dimensional surface S_1  , and a set {\cal P}_2  of n  points on a two-dimensional surface S_2  , both in {\mathbb R}^3  , the number of distinct distances between the two sets is \Omega(n/\sqrt{\log n})  (or at least \Omega(n^{1-\varepsilon})  ?).

Assuming that the conjecture is true, we have the following natural question.

Problem. Characterize which pairs of surfaces S_1,S_2  can yield O(n)  distinct distances. Moreover, provide a lower bound for the minimum number of distinct distances for the case of any other pair of surfaces.

This problem formulation is motivated by aforementioned result of Pach and de Zeeuw for the case of points on two planar curves, where the only “exceptional” cases are when the two curves contain parallel lines or concentric circles, and then the number of distinct distances can be \Theta(n)  . For any other pair of curves, the number of distinct distances is \Omega(n^{4/3})  .

Advertisements

5 thoughts on “Distinct Distances: Open Problems and Current Bounds

  1. Hi Adam,

    For two parallel planes, it seems that the conjecture follows from Guth-Katz, since in the Elekes-Sharir set up, it suffices to consider isometries that fix the planes. That is, if a,b are points in the plane z=0, and p,q are points in the plane z=1, then d(a,p)=d(b,q) IFF there exists a translation T parallel to the xy-plane and a rotation R about a vertical axis such that Ra+T=b and Rp+T=q. (Of course, more rotations could work, but this family of rotations suffices to describe congruent segments.)

    There might be a way to generalize this argument to general S_1 and S_2, although it doesn’t seem completely straight forward (heuristically, if the set of transformations mapping a in S_1 to b in S_1 can be described using 4 parameters, then a transverse 3D variety (e.g. associated to pairs of points from S_2) should intersect this 4D space in a curve; 4D might suffice by an observation of Misha Rudnev, that you can match/overlay congruent line segments using a translation, followed by a rotation about the y-axis, followed by a rotation about the z-axis, similar to spherical coordinates, requiring 4 parameter if the set of translations is 2D). Although as you point out, if the planes aren’t parallel, you might expect to do better than n/log n.

    Best,
    Brendan

  2. Hi Brendan,

    Frank and I were playing a bit with a similar idea in IPAM. If you have two planes P_1,P_2 (not necessarily parallel), let T be a rigid motion that maps P_1 to P_2. Now, every rigid motion in {\mathbb R}^3 that takes P_1 to P_2 can be written as T composed with a rigid motion from P_2 to itself. That is, we have a three-dimensional parametrization of the relevant motions. I assume that this leads to the exact same problem as in the Guth-Katz paper, and thus to the same bound, but I never fully wrote all of the details.

    Something similar can be done also for the case of two spheres, but I don’t know anything regarding any other types of surfaces.

    I’m not sure that I understand your argument regarding 4d space. The general set of motions in 3d is six-dimensional, and the set of rotations taking a point a to a point b is three-dimensional, no? Or did you refer to some other type of parametrization?

    Best,
    Adam

  3. Sorry, I think the 2nd part may be incorrect. It seems that I cannot remember Misha’s idea, but in general terms, the idea is to use a special parameterization to replace the 3D set of transformations mapping a —> b, with a 2D set of transformations in a way that is consistent for all pairs. I’ll try to get back to you with an answer.

    Best,
    Brendan

  4. Hey Adam and Brendan,
    Here is an easier way to see why Guth-Katz solves the case of two parallel planes.
    Assume the planes are z=0 and z=1. Then the square of the distance between (a,b,0) and (c,d,1) is just the distance between (a,b) and (c,d) plus 1. So you may as well leave out the 1.
    Best,
    Frank

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