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 . 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 and , and are interested only in distinct distances that are spanned by pairs of (i.e., distances between points from different sets). For simplicity, in this post we assume that both sets are of cardinality . 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 and is
In , 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 , the minimum number of distinct distances between a set of points on a two-dimensional surface , and a set of points on a two-dimensional surface .
Before we properly formulate any questions for this scenario, let us first consider some examples. First, consider the case where and are non-parallel planes in . In this case there exist two orthogonal lines such that , , and is a point on . We can place the two sets of points on such that the number of distinct distances between the two sets is (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 and are parallel planes. In this case we can place a subset of the integer lattice on each of the planes. For example, we may assume that the planes are defined by and , and that the points of the two sets are
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 .
Unlike the planar case, it is not immediately clear whether the above examples are tight. For example, the integer lattice determines only distinct distances. This leads to the following conjecture.
Conjecture. Given a set of points on a two-dimensional surface , and a set of points on a two-dimensional surface , both in , the number of distinct distances between the two sets is (or at least ?).
Assuming that the conjecture is true, we have the following natural question.
Problem. Characterize which pairs of surfaces can yield 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 . For any other pair of curves, the number of distinct distances is .