Today I wish to discuss several problems concerning finding a subset of a point set , such that the points of do not span any distance more than once. This is another family of problems for my survey of open variants of the distinct distances problem. I also present a surprisingly short and elegant proof that was recently observed by Charalambides (and is a simple combination of a proof by Lefmann and Thiele with a result from Guth and Katz’s distinct distances paper). The following table lists the best known bounds for the problems that are presented in this post.
|Variant||Lower Bound||Upper Bound|
Given a set of points in , let denote the size of the largest subset such that every distance is spanned by the points of at most once; that is, there are no points such that (including cases where ). The following figure depicts a set of 25 points and a subset of 5 points that span every distance at most once.
Let . In other words, is the maximum number satisfying the property that every set of points in the plane contains a subset of points that do not span any distance more than once. Erdős posed the following problem (see here (in Hungarian), here, and here (page 838)).
Problem 1. (Erdős) Find the asymptotic value of .
Let be a point set that spans distinct distances. Notice that if all of the distances that are spanned by the points of a subset are unique, then . Let be a integer lattice. Erdős proved that the number of distinct distances that are spanned by is (for more details see this post). Therefore, we have . Lefmann and Thiele derived the bound by using a probabilistic argument. Dumitrescu improved this bound to by combining it with an upper bound of Pach and Tardos on the maximum number of isosceles triangles that can be spanned by a set of points. Recently, Charalambides combined the probabilistic argument of Lefmann and Thiele with a result from Guth and Katz’s distinct distances paper, to obtain the following improved result and simple proof.
Proof. Consider a set of points in . Similarly to the Elekes-Sharir reduction (e.g., see this post), we define the set
such that every quadruple of consists of four distinct points. Guth and Katz proved that (also for the case where is allowed to contain quadruples where not all four points are distinct). Let be the set of isosceles and equilateral triangles that are spanned by points of . Pach and Tardos proved that .
Let be a subset that is obtained by selecting every point of with probability that we will fix later. We have . Let be the set of quadruples of that contain only points of . Every quadruple of is in with a probability of , so , for a sufficiently large constant . Let be the set of triangles of that contain only points of . The bound of Pach and Tardos implies , for a sufficiently large constant . Notice that the points of span every distance at most once if and only if . By linearity of expectation, we have
By setting , when is sufficiently larger we obtain
Therefore, there exists a subset for which . Let be a subset of that is obtained by removing from a point from every element of and . The subset does not span any repeated distances and contains points, concluding the proof.