Distinct Distances for Sets with no Repeated Bisectors

This post is about a distinct distances problem which I think is quite interesting. As we shall see, solving this problem would also lead to significant progress in characterizing point sets with a small number of distinct distances. Recall that a perpendicular bisector of two points p,q\in {\mathbb R}^2  is the line that consists of the points a  satisfying |pa|=|qa|  (where |pa|  is the distance between a  and p  ). For brevity, we will simply refer to these as bisectors.

bisectors

We say that a set {\cal P}  of n  points in {\mathbb R}^2  has no repeated bisectors if for every four distinct points a,b,c,d\in {\cal P}  the bisector of a  and b  is not identical to the bisector of c  and d  (that is, the configuration in the above figure is forbidden).

Conjecture. Let {\cal P}  be a set of n  points in {\mathbb R}^2  with no repeated bisectors. Then for any \varepsilon>0  the points of {\cal P}  determine \Omega(n^{2-\varepsilon})  distinct distances, .

Update July 2017: The conjecture is false, as pointed out by Cosmin Pohoata. A known construction is a counterexample, and I should be ashamed for not observing this on my own. Erdős, Füredi, Pach, and Ruzsa constructed a set of n  points in {\mathbb R}^2  with O(n^{1+\varepsilon})  distinct distances for any \varepsilon >0  and no four points on a common circle. Having a repeated bisector requires having four points on a circle, so there are no repeated bisectors. Oh well…

For some initial intuition, consider the point sets that determine a small number of distinct distances. I am only aware of two types of configurations that yield O(n)  distinct distances: the vertices of a regular n  -gon and lattices.

intGridnGon

We can also play a bit with these examples. For example, by taking two regular n  -gons whose vertices are on two concentric circles, or by taking n  evenly spaced points on a line (that is, an n\times 1  lattice). All of these examples have a significantly large amount of repeated bisectors.

So far I only managed to find a set with no repeated bisectors and O(\frac{n^2}{\sqrt{\lg n}})  distinct distances. From the other direction, I can only show that every such set determines \Omega(n)  distinct distances. This is unfortunate, since a stronger bound for this problem would lead to a breakthrough in characterizing planar point sets that determine a small number of distinct distances. Below I describe how this can be done, and also how to obtain simple lower and upper bounds for this problem.

Upper bound. We first describe a slightly sub-quadratic upper bound for the problem. This is a variant of a bound by Dumitrescu. First, recall that an n\times n  section of the integer lattice determines n^2/\sqrt{\lg n}  (e.g., see here). For a prime n  , we consider the set {\cal P} = \{(a,a^2) :\, 0\le a \le n-1 \}  . We work \mod n  , so the y  -coordinates are actually a^2 \mod n  . Since this is a subset of an n \times n  section of the integer lattice, the number of distinct distances that are determined by {\cal P}  is O(n^2/\sqrt{\lg n})  . If two pairs of points define the same bisector, then all four points are on a common circle. Dumitrescu showed that no four points of \cal P are on a common circle. Thus, {\cal P}  has no repeated bisectors.

BisectorCircle

Lower bound. We now discuss the (straightforward) lower bound for the problem. Let {\cal P}  be a set of n  points with no repeated bisectors, and let x  be the number of distinct distances determined by \cal P  . We set T = \{(a,b,c)\in {\cal P}^3 :\, |ab|=|ac| \}  . That is, |T|  is the number of isosceles triangles with vertices in \cal P  (where an equilateral triangle is counted three times). A simple Cauchy-Schwarz argument implies |T|= \Omega\left(\frac{n^3}{x}\right)  (e.g., see Lemma 3.1 in this survey). On the other hand, a triple (a,b,c)\in {\cal P}^3  is in T  if and only if the perpendicular bisector of b  and c  is incident to a  . Since there are n  points and \Theta(n^2)  bisectors, the Szemerédi–Trotter theorem implies that there are O(n^2)  incidences. This is not true for arbitrary point sets, since the bisectors might not be distinct, in which case we cannot apply the Szemerédi–Trotter theorem. In our case this argument works because there are no repeated bisectors. That is, we have |T| = O(n^2)  . Combining this with the above lower bound for |T|  implies x=\Omega(n)  , as asserted.

It is not surprising that it is difficult to obtain a bound of \Omega(n^{1+\varepsilon})  distinct distances, since this is actually a more general variant of an existing distinct distances problem with no non-trivial bounds for it. Specifically, Erdős asked for the minimum number of distinct distances that a point set can determine if every four points of the set determine at least five distances (for more details about this problem and related ones, see this older post). Even though the point set is more restricted in this older problem, which has been mentioned in several places over the past several decades, no non-trivial bound is known for it (Larry Guth recently pointed out this observation to me).

Reduction. One of the main open problems concerning distinct distances is characterizing the point sets in {\mathbb R}^2  that determine O(n/\sqrt{\log n})  distinct distances. I already discussed this problem in detail in a previous post. Let me just mention that the first step towards solving the problem seems to be proving the following claim: If an n  -point set {\cal P}  determines O(n/\sqrt{\lg n})  distinct distances, then there exists a line that contains \Omega(n^\varepsilon)  point of \cal P  . Embarrassingly, so far we only know how to prove the existence of a line with \Omega(\lg n)  points of \cal P  on it.

In a paper by Ben Lund, Frank de Zeeuw, and myself, we studied the bisector energy of a point set \cal P  . This is the quantity

E(P) = \left|\{ (a,b,c,d) :\, a,b \text{ have the same bisector as } c,d \}\right|.

In this definition, we do not count quadruples (a,b,c,d)  where (a,b)  is the same pair as (c,d)  . That is, it is possible to have E({\cal P})=0  . In the paper we prove that if no line or circle contains \Omega(m)  points of \cal P  , then for any for any \varepsilon >0  we have E({\cal P}) = O(m^{2/3}n^{12/5 +\varepsilon} + mn^2)  .

Assume for contradiction that there exists an n  -point set \cal P  with O(n/\sqrt{\lg n})  distinct distances and with no line or circle containing \Omega(n^{\varepsilon})  points of {\cal P}  . The aforementioned result implies that E({\cal P}) = O(n^{12/5+\varepsilon})  . Let p=1/(2n^{7/15})  and let {\cal P}'  be a set that is obtained by taking each point of \cal P  with probability p  . By a standard probabilistic argument we obtain that there exists such a subset {\cal P}'  satisfying |{\cal P}'| - E({\cal P}') = \Omega(n^{8/15-\varepsilon})  (we omit the straightforward calculation). Let {\cal P}''  be the set obtained by removing from {\cal P}'  an arbitrary point from each quadruple that contributes to E({\cal P}')  . That is, {\cal P}''  is a set of \Omega(n^{8/15-\varepsilon})  points of \cal P  with no repeated bisectors.

This leads to the above conjecture. Specifically, if every n  -point set with no repeated bisectors determines \Omega(n^{15/8+\varepsilon})  distinct distances, then {\cal P}''  determines \Omega(n)  distinct distances. This would contradict the assumption that \cal P  determines O(n/\sqrt{\lg n})  distinct distances, and imply that there must exist a line or a circle that contains \Omega(n^\varepsilon)  points of \cal P  .

While the above argument requires the rather strong bound of \Omega(n^{15/8+\varepsilon})  distinct distances, a weaker bound may also suffice. This is because the aforementioned upper bound E({\cal P}) = O(m^{2/3}n^{12/5 +\varepsilon} + mn^2)  seems far from tight (we conjecture that the correct bound is E({\cal P}) = O(mn^2)  ). Improving this bound would lead to weaker requirements for the number of distinct distances.

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