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.


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.


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.

Continue reading